{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Ways of Cutting a Pizza"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ways"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #切披萨的方案数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>rows x cols</code>&nbsp;大小的矩形披萨和一个整数 <code>k</code>&nbsp;，矩形包含两种字符：&nbsp;<code>&#39;A&#39;</code> （表示苹果）和&nbsp;<code>&#39;.&#39;</code>&nbsp;（表示空白格子）。你需要切披萨 <code>k-1</code> 次，得到&nbsp;<code>k</code>&nbsp;块披萨并送给别人。</p>\n",
    "\n",
    "<p>切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。</p>\n",
    "\n",
    "<p>请你返回确保每一块披萨包含&nbsp;<strong>至少</strong>&nbsp;一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/10/ways_to_cut_apple_1.png\" style=\"height: 378px; width: 500px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>pizza = [&quot;A..&quot;,&quot;AAA&quot;,&quot;...&quot;], k = 3\n",
    "<strong>输出：</strong>3 \n",
    "<strong>解释：</strong>上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>pizza = [&quot;A..&quot;,&quot;AA.&quot;,&quot;...&quot;], k = 3\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>pizza = [&quot;A..&quot;,&quot;A..&quot;,&quot;...&quot;], k = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rows, cols &lt;= 50</code></li>\n",
    "\t<li><code>rows ==&nbsp;pizza.length</code></li>\n",
    "\t<li><code>cols ==&nbsp;pizza[i].length</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10</code></li>\n",
    "\t<li><code>pizza</code>&nbsp;只包含字符&nbsp;<code>&#39;A&#39;</code>&nbsp;和&nbsp;<code>&#39;.&#39;</code>&nbsp;。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-ways-of-cutting-a-pizza](https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-ways-of-cutting-a-pizza](https://leetcode.cn/problems/number-of-ways-of-cutting-a-pizza/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"A..\",\"AAA\",\"...\"]\\n3', '[\"A..\",\"AA.\",\"...\"]\\n3', '[\"A..\",\"A..\",\"...\"]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        if k >= n:\n",
    "            return -1\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in highways:\n",
    "            g[a].append((b, cost))\n",
    "            g[b].append((a, cost))\n",
    "        f = [[-inf] * n for _ in range(1 << n)]\n",
    "        for i in range(n):\n",
    "            f[1 << i][i] = 0\n",
    "        ans = -1\n",
    "        for i in range(1 << n):\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    for h, cost in g[j]:\n",
    "                        if i >> h & 1:\n",
    "                            f[i][j] = max(f[i][j], f[i ^ (1 << j)][h] + cost)\n",
    "                if i.bit_count() == k + 1:\n",
    "                    ans = max(ans, f[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict,deque\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param highways:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in highways:\n",
    "            m1[i[0]].append((i[1], i[2]))\n",
    "            m1[i[1]].append((i[0], i[2]))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check_max(start, used):\n",
    "            if len(used) == k + 1:\n",
    "                return 0\n",
    "\n",
    "            ans = -math.inf\n",
    "            for i in m1[start]:\n",
    "                if i[0] not in used:\n",
    "                    ans = max(ans, i[1] + check_max(i[0], used.union({i[0]})))\n",
    "            return ans\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            ans1 = check_max(i, frozenset({i}))\n",
    "            ans = max(ans, ans1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maximumCost( n = 4, highways = [[0,1,3],[2,3,2]], k = 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import defaultdict,deque\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param highways:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 = defaultdict(list)\n",
    "        for i in highways:\n",
    "            m1[i[0]].append((i[1], i[2]))\n",
    "            m1[i[1]].append((i[0], i[2]))\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check_max(start, used):\n",
    "            if len(used) == k + 1:\n",
    "                return 0\n",
    "\n",
    "            ans = -math.inf\n",
    "            for i in m1[start]:\n",
    "                if i[0] not in used:\n",
    "                    ans = max(ans, i[1] + check_max(i[0], used.union({i[0]})))\n",
    "            return ans\n",
    "\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            ans1 = check_max(i, frozenset({i}))\n",
    "            ans = max(ans, ans1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:\n",
    "        graph = defaultdict(dict)\n",
    "        for a, b, c in highways:\n",
    "            graph[a][b] = c\n",
    "            graph[b][a] = c\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, explored):\n",
    "            if explored.bit_count() == k + 1:\n",
    "                return 0\n",
    "\n",
    "            ans = -inf\n",
    "            for other, v in graph[cur].items():\n",
    "                if not explored & (o := 1 << other):\n",
    "                    ans = max(ans, dfs(other, explored | o) + v)\n",
    "            return ans\n",
    "\n",
    "        return max(-1, max(dfs(i, 1 << i) for i in range(n)))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pathsWithMaxScore(self, board: List[str]) -> List[int]:\n",
    "       n = len(board)\n",
    "       ways = [[0] * n for _ in range(n)]\n",
    "       ways[n - 1][n - 1] = 1\n",
    "       MOD = 10 ** 9 + 7\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int, j: int) -> int:\n",
    "          if i == n - 1 and j == n - 1:\n",
    "             return 0\n",
    "          if board[i][j] == 'X':\n",
    "             return -inf\n",
    "          res1 = -inf\n",
    "          res2 = -inf\n",
    "          res3 = -inf\n",
    "          if i + 1 < n:\n",
    "             res1 = dfs(i + 1, j)\n",
    "          if j + 1 < n:\n",
    "             res2 = dfs(i, j + 1)\n",
    "          if i + 1 < n and j + 1 < n:\n",
    "             res3 = dfs(i + 1, j + 1)\n",
    "          res = max(res1, res2, res3)\n",
    "          if res != -inf:\n",
    "             if res == res1:\n",
    "                ways[i][j] += ways[i + 1][j]\n",
    "                ways[i][j] %= MOD\n",
    "             if res == res2:\n",
    "                ways[i][j] += ways[i][j + 1]\n",
    "                ways[i][j] %= MOD\n",
    "             if res == res3:\n",
    "                ways[i][j] += ways[i + 1][j + 1]\n",
    "                ways[i][j] %= MOD\n",
    "          if not (i == 0 and j == 0):\n",
    "             res += ord(board[i][j]) - ord('0')\n",
    "          return res\n",
    "       res = dfs(0, 0)\n",
    "       if res < 0:\n",
    "          return [0, 0]\n",
    "       return [res, ways[0][0]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[0 for j in range(n + 1)] for i in range(m + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[i][j] = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for _ in range(2, k + 1):\n",
    "            col_s = [0] * n\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                row_s = 0\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    tmp = dp[i][j]\n",
    "                    if apples[i][j] == apples[i][j + 1]:\n",
    "                        dp[i][j] = dp[i][j + 1]\n",
    "                    elif apples[i][j] == apples[i + 1][j]:\n",
    "                        dp[i][j] = dp[i + 1][j]\n",
    "                    else:\n",
    "                        dp[i][j] = (row_s + col_s[j]) % mod\n",
    "                    row_s += tmp\n",
    "                    col_s[j] += tmp\n",
    "        return dp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]  # 二维后缀和\n",
    "\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "\n",
    "            for j in range(n - 1, -1, -1):\n",
    "\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "\n",
    "                if s[i][j]: f[i][j] = 1  # 初始值\n",
    "\n",
    "\n",
    "\n",
    "        for _ in range(1, k):\n",
    "\n",
    "            col_s = [0] * n  # col_s[j] 表示 f 第 j 列的后缀和\n",
    "\n",
    "            for i in range(m - 1, -1, -1):\n",
    "\n",
    "                row_s = 0  # f[i] 的后缀和\n",
    "\n",
    "                for j in range(n - 1, -1, -1):\n",
    "\n",
    "                    tmp = f[i][j]\n",
    "\n",
    "                    if s[i][j] == s[i][j + 1]:  # 左边界没有苹果\n",
    "\n",
    "                        f[i][j] = f[i][j + 1]\n",
    "\n",
    "                    elif s[i][j] == s[i + 1][j]:  # 上边界没有苹果\n",
    "\n",
    "                        f[i][j] = f[i + 1][j]\n",
    "\n",
    "                    else:  # 左边界上边界都有苹果，那么无论怎么切都有苹果\n",
    "\n",
    "                        f[i][j] = (row_s + col_s[j]) % MOD\n",
    "\n",
    "                    row_s += tmp\n",
    "\n",
    "                    col_s[j] += tmp\n",
    "\n",
    "        return f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]  # 二维后缀和\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                if s[i][j]: f[i][j] = 1  # 初始值\n",
    "\n",
    "        for _ in range(1, k):\n",
    "            col_s = [0] * n  # col_s[j] 表示 f 第 j 列的后缀和\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                row_s = 0  # f[i] 的后缀和\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    tmp = f[i][j]\n",
    "                    if s[i][j] == s[i][j + 1]:  # 左边界没有苹果\n",
    "                        f[i][j] = f[i][j + 1]\n",
    "                    elif s[i][j] == s[i + 1][j]:  # 上边界没有苹果\n",
    "                        f[i][j] = f[i + 1][j]\n",
    "                    else:  # 左边界上边界都有苹果，那么无论怎么切都有苹果\n",
    "                        f[i][j] = (row_s + col_s[j]) % MOD\n",
    "                    row_s += tmp\n",
    "                    col_s[j] += tmp\n",
    "        return f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        rows=len(pizza)\n",
    "        cols=len(pizza[0])\n",
    "        sum_matrix=[[0 for ii in range(cols)] for i in range(rows)]\n",
    "        res_matrix=[[0 for ii in range(cols)] for i in range(rows)]\n",
    "        sum_matrix[rows-1][cols-1]=int(pizza[rows-1][cols-1]==\"A\")\n",
    "        for j in range(cols-2,-1,-1):\n",
    "            sum_matrix[rows-1][j]=sum_matrix[rows-1][j+1]+(pizza[rows-1][j]=='A')\n",
    "        for i in range(rows-2,-1,-1):\n",
    "            sum_matrix[i][cols-1]=sum_matrix[i+1][cols-1]+(pizza[i][cols-1]=='A')\n",
    "            for j in range(cols-2,-1,-1):\n",
    "                sum_matrix[i][j]=sum_matrix[i][j+1]+sum_matrix[i+1][j]-sum_matrix[i+1][j+1]+(pizza[i][j]=='A')\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if(sum_matrix[i][j]):\n",
    "                    res_matrix[i][j]=1\n",
    "        for cal_time in range(k-1):\n",
    "            col_sum=[0 for i in range(cols)]\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                row_sum=0\n",
    "                for j in range(cols-1,-1,-1):\n",
    "                    tmp=res_matrix[i][j]\n",
    "                    if(i<rows-1 and sum_matrix[i][j]==sum_matrix[i+1][j]):\n",
    "                        res_matrix[i][j]=res_matrix[i+1][j]\n",
    "                    elif(j<cols-1 and sum_matrix[i][j]==sum_matrix[i][j+1]):\n",
    "                        res_matrix[i][j]=res_matrix[i][j+1]\n",
    "                    else:\n",
    "                        res_matrix[i][j]=(col_sum[j]+row_sum)%MOD\n",
    "                    row_sum+=tmp\n",
    "                    col_sum[j]+=tmp\n",
    "        return int(res_matrix[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # 这里用的是后缀和数组\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]  # 二维后缀和\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                if s[i][j]: f[i][j] = 1  # 初始值\n",
    "\n",
    "        for _ in range(1, k):\n",
    "            col_s = [0] * n  # col_s[j] 表示 f 第 j 列的后缀和\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                row_s = 0  # f[i] 的后缀和\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    tmp = f[i][j]\n",
    "                    if s[i][j] == s[i][j + 1]:  # 左边界没有苹果\n",
    "                        f[i][j] = f[i][j + 1]\n",
    "                    elif s[i][j] == s[i + 1][j]:  # 上边界没有苹果\n",
    "                        f[i][j] = f[i + 1][j]\n",
    "                    else:  # 左边界上边界都有苹果，那么无论怎么切都有苹果\n",
    "                        f[i][j] = (row_s + col_s[j]) % MOD\n",
    "                    row_s += tmp\n",
    "                    col_s[j] += tmp\n",
    "        return f[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]  # 二维后缀和\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                if s[i][j]: f[i][j] = 1  # 初始值\n",
    "\n",
    "        for _ in range(1, k):\n",
    "            col_s = [0] * n  # col_s[j] 表示 f 第 j 列的后缀和\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                row_s = 0  # f[i] 的后缀和\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    tmp = f[i][j]\n",
    "                    if s[i][j] == s[i][j + 1]:  # 左边界没有苹果\n",
    "                        f[i][j] = f[i][j + 1]\n",
    "                    elif s[i][j] == s[i + 1][j]:  # 上边界没有苹果\n",
    "                        f[i][j] = f[i + 1][j]\n",
    "                    else:  # 左边界上边界都有苹果，那么无论怎么切都有苹果\n",
    "                        f[i][j] = (row_s + col_s[j]) % MOD\n",
    "                    row_s += tmp\n",
    "                    col_s[j] += tmp\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]  # 二维后缀和\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                if s[i][j]: f[i][j] = 1  # 初始值\n",
    "\n",
    "        for _ in range(1, k):\n",
    "            col_s = [0] * n  # col_s[j] 表示 f 第 j 列的后缀和\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                row_s = 0  # f[i] 的后缀和\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    tmp = f[i][j]\n",
    "                    if s[i][j] == s[i][j + 1]:  # 左边界没有苹果\n",
    "                        f[i][j] = f[i][j + 1]\n",
    "                    elif s[i][j] == s[i + 1][j]:  # 上边界没有苹果\n",
    "                        f[i][j] = f[i + 1][j]\n",
    "                    else:  # 左边界上边界都有苹果，那么无论怎么切都有苹果\n",
    "                        f[i][j] = (row_s + col_s[j]) % MOD\n",
    "                    row_s += tmp\n",
    "                    col_s[j] += tmp\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]  # 二维后缀和\n",
    "        f = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                s[i][j] = s[i][j + 1] + s[i + 1][j] - s[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                if s[i][j]: f[i][j] = 1  # 初始值\n",
    "\n",
    "        for _ in range(1, k):\n",
    "            col_s = [0] * n  # col_s[j] 表示 f 第 j 列的后缀和\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                row_s = 0  # f[i] 的后缀和\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    tmp = f[i][j]\n",
    "                    if s[i][j] == s[i][j + 1]:  # 左边界没有苹果\n",
    "                        f[i][j] = f[i][j + 1]\n",
    "                    elif s[i][j] == s[i + 1][j]:  # 上边界没有苹果\n",
    "                        f[i][j] = f[i + 1][j]\n",
    "                    else:  # 左边界上边界都有苹果，那么无论怎么切都有苹果\n",
    "                        f[i][j] = (row_s + col_s[j]) % MOD\n",
    "                    row_s += tmp\n",
    "                    col_s[j] += tmp\n",
    "        return f[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        rows=len(pizza)\n",
    "        cols=len(pizza[0])\n",
    "        sum_matrix=[[0 for ii in range(cols)] for i in range(rows)]\n",
    "        res_matrix=[[0 for ii in range(cols)] for i in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if(pizza[i][j]=='A'):\n",
    "                    sum_matrix[i][j]=1\n",
    "        for j in range(cols-2,-1,-1):\n",
    "            sum_matrix[rows-1][j]+=sum_matrix[rows-1][j+1]\n",
    "        for i in range(rows-2,-1,-1):\n",
    "            sum_matrix[i][cols-1]+=sum_matrix[i+1][cols-1]\n",
    "            for j in range(cols-2,-1,-1):\n",
    "                sum_matrix[i][j]+=sum_matrix[i][j+1]+sum_matrix[i+1][j]-sum_matrix[i+1][j+1]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if(sum_matrix[i][j]):\n",
    "                    res_matrix[i][j]=1\n",
    "        for cal_time in range(k-1):\n",
    "            col_sum=[0 for i in range(cols)]\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                row_sum=0\n",
    "                for j in range(cols-1,-1,-1):\n",
    "                    tmp=res_matrix[i][j]\n",
    "                    if(i<rows-1 and sum_matrix[i][j]==sum_matrix[i+1][j]):\n",
    "                        res_matrix[i][j]=res_matrix[i+1][j]\n",
    "                    elif(j<cols-1 and sum_matrix[i][j]==sum_matrix[i][j+1]):\n",
    "                        res_matrix[i][j]=res_matrix[i][j+1]\n",
    "                    else:\n",
    "                        res_matrix[i][j]=(col_sum[j]+row_sum)%MOD\n",
    "                    row_sum+=tmp\n",
    "                    col_sum[j]+=tmp\n",
    "        return int(res_matrix[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        #copy 0x3\n",
    "        MOD = 10**9+7\n",
    "        m,n = len(pizza),len(pizza[0])\n",
    "        s= [[0]*(n+1) for i in range(m+1)]\n",
    "        f= [[0]*(n+1) for i in range(m+1)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                s[i][j] = s[i][j+1] + s[i+1][j] - s[i+1][j+1] +(pizza[i][j] == 'A')\n",
    "                if s[i][j]:\n",
    "                    f[i][j] =1\n",
    "        \n",
    "        for _ in range(1,k):\n",
    "            cols = [0]*n\n",
    "            for i in range(m-1,-1,-1):\n",
    "                rows = 0\n",
    "                for j in range(n-1,-1,-1):\n",
    "                    tmp = f[i][j]\n",
    "                    if s[i][j] == s[i][j+1]:\n",
    "                        f[i][j] = f[i][j+1]\n",
    "                    elif s[i][j] == s[i+1][j]:\n",
    "                        f[i][j] = f[i+1][j]\n",
    "                    else:\n",
    "                        f[i][j] = (rows+cols[j])%MOD\n",
    "                    rows  += tmp\n",
    "                    cols[j] += tmp\n",
    "        return f[0][0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        rows=len(pizza)\n",
    "        cols=len(pizza[0])\n",
    "        sum_matrix=[[0 for ii in range(cols)] for i in range(rows)]\n",
    "        res_matrix=[[0 for ii in range(cols)] for i in range(rows)]\n",
    "        sum_matrix[rows-1][cols-1]=int(pizza[rows-1][cols-1]==\"A\")\n",
    "        for j in range(cols-2,-1,-1):\n",
    "            sum_matrix[rows-1][j]=sum_matrix[rows-1][j+1]+(pizza[rows-1][j]=='A')\n",
    "        for i in range(rows-2,-1,-1):\n",
    "            sum_matrix[i][cols-1]=sum_matrix[i+1][cols-1]+(pizza[i][cols-1]=='A')\n",
    "            for j in range(cols-2,-1,-1):\n",
    "                sum_matrix[i][j]=sum_matrix[i][j+1]+sum_matrix[i+1][j]-sum_matrix[i+1][j+1]+(pizza[i][j]=='A')\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if(sum_matrix[i][j]):\n",
    "                    res_matrix[i][j]=1\n",
    "        for cal_time in range(k-1):\n",
    "            col_sum=[0 for i in range(cols)]\n",
    "            for i in range(rows-1,-1,-1):\n",
    "                row_sum=0\n",
    "                for j in range(cols-1,-1,-1):\n",
    "                    tmp=res_matrix[i][j]\n",
    "                    if(i<rows-1 and sum_matrix[i][j]==sum_matrix[i+1][j]):\n",
    "                        res_matrix[i][j]=res_matrix[i+1][j]\n",
    "                    elif(j<cols-1 and sum_matrix[i][j]==sum_matrix[i][j+1]):\n",
    "                        res_matrix[i][j]=res_matrix[i][j+1]\n",
    "                    else:\n",
    "                        res_matrix[i][j]=(col_sum[j]+row_sum)%MOD\n",
    "                    row_sum+=tmp\n",
    "                    col_sum[j]+=tmp\n",
    "        return int(res_matrix[0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution():\n",
    "\tdef ways(self, pizza: List[str], k: int) -> int:\n",
    "\t\tm=len(pizza)\n",
    "\t\tn=len(pizza[0])\n",
    "\n",
    "\t\t# 初始化前缀和数组\n",
    "\t\tapples=[[0 for i in range(n+1)] for j in range(m+1)]\n",
    "\t\tfor i in range(m):\n",
    "\t\t\tfor j in range(n):\n",
    "\t\t\t\tapples[m-1-i][n-1-j]=apples[m-i][n-1-j]+apples[m-1-i][n-j]-apples[m-i][n-j]+(pizza[m-1-i][n-1-j] == \"A\")\n",
    "\n",
    "\t\t# 定义优化数组\n",
    "\t\tdps1=[[0 for i in range(n)] for j in range(m)]\n",
    "\t\tdps2=[[1 if apples[i][j] > 0 else 0 for j in range(n)] for i in range(m)]\n",
    "\t\tfor c in range(k-1):\n",
    "\t\t\tfor i in range(m):\n",
    "\t\t\t\tfor j in range(n):\n",
    "\t\t\t\t\tres=0\n",
    "\t\t\t\t\tfor _i in range(i+1,m):\n",
    "\t\t\t\t\t\tres+=dps2[_i][j] if apples[i][j] > apples[_i][j] else 0\n",
    "\t\t\t\t\tfor _j in range(j+1,n):\n",
    "\t\t\t\t\t\tres+=dps2[i][_j] if apples[i][j] > apples[i][_j] else 0\n",
    "\t\t\t\t\tdps1[i][j]=res\n",
    "\t\t\tdps1,dps2=dps2,dps1\n",
    "\n",
    "\t\treturn dps2[0][0] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        A = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                left = A[i][j - 1] if j > 0 else 0 \n",
    "                up = A[i - 1][j] if i > 0 else 0 \n",
    "                corner = A[i - 1][j - 1] if i > 0 and j > 0 else 0 \n",
    "                A[i][j] = left + up - corner + (pizza[i][j] == 'A')\n",
    "        if not A[-1][-1]:\n",
    "            return 0\n",
    "        def check(r1, c1, r2, c2):\n",
    "            left = A[r2][c1 - 1] if c1 > 0 else 0 \n",
    "            up = A[r1 - 1][c2] if r1 > 0 else 0 \n",
    "            corner = A[r1 - 1][c1 - 1] if r1 > 0 and c1 > 0 else 0 \n",
    "            return A[r2][c2] - left - up + corner > 0 \n",
    "        dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0] = 1 \n",
    "        for _ in range(2, k + 1):\n",
    "            new = [[0 for _ in range(n)] for _ in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for h in range(i + 1, m):\n",
    "                        if check(i, j, h - 1, n - 1) and check(h, j, m - 1, n - 1):\n",
    "                            new[h][j] += dp[i][j]\n",
    "                    for v in range(j + 1, n):\n",
    "                        if check(i, j, m - 1, v - 1) and check(i, v, m - 1, n - 1):\n",
    "                            new[i][v] += dp[i][j]\n",
    "            dp = new \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res += dp[i][j]\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        R, C = len(pizza), len(pizza[0])\n",
    "        map1 = [[1 for _ in range(C)] + [0] for _ in range(R)] + [[0 for _ in range(C + 1)]]\n",
    "        _t = -1\n",
    "        for r in range(R - 1, -1, -1):\n",
    "            c = C - 1\n",
    "            while c > _t and pizza[r][c] == '.' :\n",
    "                map1[r][c] = 0\n",
    "                c -= 1\n",
    "            _t = max(_t, c)\n",
    "\n",
    "        map2 = [[0 for _ in range(C + 1)] for _ in range(R + 1)]\n",
    "        for _ in range(k - 1):\n",
    "            for r in range(R - 1, -1, -1):\n",
    "                for c in range(C - 1, -1, -1):\n",
    "                    if pizza[r][c] == 'A':\n",
    "                        for i in range(c + 1, C):\n",
    "                            map2[r][c] += map1[r][i]\n",
    "                        for i in range(r + 1, R):\n",
    "                            map2[r][c] += map1[i][c]\n",
    "                    else:\n",
    "                        _r, _c = r, c\n",
    "                        if all(i == '.' for i in pizza[r][c: ]):\n",
    "                            _r = r + 1\n",
    "                        if all(i == '.' for i in [pizza[t][c] for t in range(r + 1, R)]):\n",
    "                            _c = c + 1\n",
    "                        if _r == r and _c == c:\n",
    "                            for i in range(c + 1, C):\n",
    "                                map2[r][c] += map1[r][i]\n",
    "                            for i in range(r + 1, R):\n",
    "                                map2[r][c] += map1[i][c]\n",
    "                        else:\n",
    "                            map2[r][c] = map2[_r][_c]\n",
    "\n",
    "            if map2[0][0] == 0: return 0\n",
    "            map1 = map2[:]\n",
    "            map2 = [[0 for _ in range(C + 1)] for _ in range(R + 1)]\n",
    "        return map1[0][0] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # 第i步\n",
    "        # 位置x，y\n",
    "        # 向左向上扩展\n",
    "        N = len(pizza)\n",
    "        M = len(pizza[0])\n",
    "        m = {}\n",
    "        # TOTAL = sum([sum([1 for c in row if c == 'A']) for row in pizza])\n",
    "        for i in range(N+1):\n",
    "            m[(i, M)] = 0\n",
    "        for i in range(M+1):\n",
    "            m[(N, i)] = 0\n",
    "        for i in range(N-1, -1, -1):\n",
    "            for j in range(M-1, -1, -1):\n",
    "                m[(i, j)] = m[(i, j+1)] + m[(i+1, j)] - m[(i+1, j+1)] + (1 if pizza[i][j] == 'A' else 0)\n",
    "        # TOTAL = m[(0, 0)]\n",
    "        if m[(0, 0)] == 0:\n",
    "            return 0\n",
    "        MODULE = int(1e9 + 7)\n",
    "        f = [[0 for _ in range(M+1)] for _ in range(N+1)]\n",
    "        f[0][0] = 1\n",
    "        for _ in range(k-1):\n",
    "            for i in range(N, -1, -1):\n",
    "                for j in range(M, -1, -1):\n",
    "                    if m[(i, j)] == 0:\n",
    "                        f[i][j] = 0\n",
    "                    else:\n",
    "                        c = 0\n",
    "                        for l in range(i):\n",
    "                            if m[(l, j)] != m[(i, j)]:\n",
    "                                c = (c + f[l][j]) % MODULE\n",
    "                        for l in range(j):\n",
    "                            if m[(i, l)] != m[(i, j)]:\n",
    "                                c = (c + f[i][l]) % MODULE\n",
    "                        f[i][j] = c\n",
    "        res = 0\n",
    "        for row in f:\n",
    "            for d in row:\n",
    "                res = (res + d) % MODULE\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        ms = MatrixSum(pizza)\n",
    "        m=len(pizza)\n",
    "        n=len(pizza[0])\n",
    "        f=[[[0]*n for _ in range(m)] for _ in range(k)]\n",
    "        for c in range(k):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if c==0:\n",
    "                        f[c][i][j]=1 if ms.query(i,j,m,n) else 0\n",
    "                        continue\n",
    "                    res=0\n",
    "                    for j2 in range(j+1,n):\n",
    "                        if ms.query(i,j,m,j2):\n",
    "                            res+=f[c-1][i][j2]\n",
    "                    for i2 in range(i+1,m):\n",
    "                        if ms.query(i,j,i2,n):\n",
    "                            res+=f[c-1][i2][j]\n",
    "                    f[c][i][j]=res%mod\n",
    "        return f[-1][0][0]\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[str]):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + (x == 'A')\n",
    "        self.s = s\n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j] = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(1, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # leetcode答案\n",
    "        # 三维动态规划+后缀和\n",
    "        \"\"\"\n",
    "        总思路：\n",
    "        三维dp：dp[o][i][j] 表示在以(i,j)为左上角,(m−1,n−1)为右下角的pizza矩阵中切o刀的可能方案数，则需返回dp[k−1][0][0]。\n",
    "        矩阵维度：m=pizza.size(),n=pizza[0].size().\n",
    "        后缀和：sub[i][j]表示以(i,j)为左上角,(m−1,n−1)为右下角的pizza矩阵中苹果的数量\n",
    "        辅助函数：x>0返回1，否则返回0，其含义是表示被切掉的部分是否有苹果，x表示切掉的pizza中的苹果数量\n",
    "        \n",
    "        边界条件：\n",
    "        - 切0刀，只要pizza矩阵上有苹果就为1，否则为0，即dp[0][i][j]=0；\n",
    "\n",
    "        \"\"\"\n",
    "        m, n, modu = len(pizza), len(pizza[0]), 1e9 + 7\n",
    "        sub = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in range(k)]\n",
    "\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                # 计算后缀和,sub为后缀和，表示以i,j为左上角，pizza右下角为右下角的矩阵中苹果的个数\n",
    "                sub[i][j] = sub[i + 1][j] + sub[i][j + 1] - sub[i + 1][j + 1] + (1 if pizza[i][j] == \"A\" else 0)\n",
    "            \n",
    "        # k = 0情况：不需要切割，只要pizza上有苹果就是可行的\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                dp[0][i][j] = 1 if sub[i][j] > 0 else 0\n",
    "\n",
    "        # i = m - 1：尾行的第j列到结尾的pizza切割o刀的可行方案数\n",
    "        for o in range(k):\n",
    "            for j in range(n - 2, -1, -1):\n",
    "                for h in range(1, n - j):\n",
    "                    dp[o][m - 1][j] += dp[o - 1][m - 1][j + h] if sub[m - 1][j] - sub[m - 1][j + h] > 0 else 0\n",
    "        \n",
    "        # j = n - 1：尾列的第i行到结尾的pizza切割o刀的可行方案数\n",
    "        for o in range(k):\n",
    "            for i in range(m - 2, -1, -1):\n",
    "                for h in range(1, m - i):\n",
    "                    dp[o][i][n - 1] += dp[o - 1][i + h][n - 1] if sub[i][n - 1] - sub[i + h][n - 1] > 0 else 0\n",
    "\n",
    "        # 一般情况：dp[o][i][j]=横切一刀后dp[o-1][i+h][j]的总和 + 竖切一刀后dp[o-1][i][j+h]的总和\n",
    "        for o in range(1, k):\n",
    "            for i in range(m - 2, -1, -1):\n",
    "                for j in range(n - 2, -1, -1):\n",
    "                    for h in range(1, m - i):\n",
    "                        dp[o][i][j] += dp[o - 1][i + h][j] if sub[i][j] - sub[i + h][j] > 0 else 0\n",
    "                    for h in range(1, n - j):\n",
    "                        dp[o][i][j] += dp[o - 1][i][j + h] if sub[i][j] - sub[i][j + h] > 0 else 0\n",
    "        \n",
    "        return int(dp[k - 1][0][0] % modu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ms = MatrixSum(pizza)\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        f = [[[0] * n for _ in range(m)] for _ in range(k)]\n",
    "        # def dfs(cn, r1, c1):\n",
    "        #     if cn == 0:\n",
    "        #         return 1 if ms.query(r1, c1, m, n) else 0\n",
    "        #     res = 0\n",
    "        #     for i in range(r1+1, m):\n",
    "        #         if ms.query(r1, c1, i, n):\n",
    "        #             res += dfs(cn - 1, i, c1)\n",
    "\n",
    "        #     for j in range(c1+1, n):\n",
    "        #         if ms.query(r1, c1, m, j):\n",
    "        #             res += dfs(cn - 1, r1, j)\n",
    "\n",
    "        #     return res % MOD\n",
    "\n",
    "        # return dfs(k - 1, 0, 0)\n",
    "\n",
    "        for cn in range(k):\n",
    "            for r1 in range(m):\n",
    "                for c1 in range(n):\n",
    "                    if cn == 0:\n",
    "                        f[cn][r1][c1] = 1 if ms.query(r1, c1, m, n) else 0\n",
    "                        continue\n",
    "                    res = 0\n",
    "                    for i in range(r1+1, m):\n",
    "                        if ms.query(r1, c1, i, n):\n",
    "                            res += f[cn-1][i][c1]\n",
    "\n",
    "                    for j in range(c1+1, n):\n",
    "                        if ms.query(r1, c1, m, j):\n",
    "                            res += f[cn-1][r1][j]\n",
    "\n",
    "                    f[cn][r1][c1] = res % MOD\n",
    "\n",
    "        return f[-1][0][0]\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[str]):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, col in enumerate(row):\n",
    "                s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + (col == \"A\")\n",
    "        self.s = s\n",
    "    \n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2][c2] - self.s[r1][c2] - self.s[r2][c1] + self.s[r1][c1]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # dp[k][i][j] 表示把坐标 (i,j)(i, j)(i,j) 右下方的披萨切割成 kkk 块披萨的方案数量，\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j] = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(1, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        # 所以大披萨的苹果数量，要严格大于小披萨苹果数量，小披萨的苹果数量，要严格大于零\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j] = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(1, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "        return dp[k][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        r,c=len(pizza),len(pizza[0])\n",
    "        apples = [[0]*(c+1) for _ in range(r+1)]\n",
    "        dp = [[[0]*c for _ in range(r)] for _ in range(k+1)]\n",
    "\n",
    "        # dp[p][i][j]表示把左上角为[i,j]右下角是[r-1,c-1]的披萨，切成p块的方案数\n",
    "        # 用二维后缀和来判断某一刀切的是否有效,即切之前的苹果应该多于切之后的苹果\n",
    "        # 在行和列都枚举所有的切法,然后统计有效的方案数\n",
    "        for i in range(r-1,-1,-1):\n",
    "            for j in range(c-1,-1,-1):\n",
    "                apples[i][j] = apples[i+1][j] + apples[i][j+1] - \\\n",
    "                    apples[i+1][j+1] + (pizza[i][j]=='A')\n",
    "                dp[1][i][j] = 1 if apples[i][j]>0 else 0\n",
    "        # 这里的后缀和是从[i, j]到右下角[r-1,c-1]的矩形中的苹果数量\n",
    "\n",
    "        for p in range(2,k+1):\n",
    "            for i in range(r):\n",
    "                for j in range(c):\n",
    "                    for i2 in range(i+1,r):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[p][i][j] = (dp[p][i][j] + dp[p-1][i2][j])%MOD\n",
    "                    for j2 in range(j+1,c):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[p][i][j] = (dp[p][i][j] + dp[p-1][i][j2])%MOD\n",
    "                    # if p==k: break\n",
    "                # if p==k: break\n",
    "                # 因为最后是要dp[k][0][0]的答案,所以循环到p=k的时候,只需要跑一次i=0 j=0就行了\n",
    "                # 后面的可以不跑直接break\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j] = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(1, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        r,c=len(pizza),len(pizza[0])\n",
    "        apples = [[0]*(c+1) for _ in range(r+1)]\n",
    "        dp = [[[0]*c for _ in range(r)] for _ in range(k+1)]\n",
    "\n",
    "        for i in range(r-1,-1,-1):\n",
    "            for j in range(c-1,-1,-1):\n",
    "                apples[i][j] = apples[i+1][j] + apples[i][j+1] - \\\n",
    "                    apples[i+1][j+1] + (pizza[i][j]=='A')\n",
    "                dp[1][i][j] = 1 if apples[i][j]>0 else 0\n",
    "\n",
    "        for p in range(2,k+1):\n",
    "            for i in range(r):\n",
    "                for j in range(c):\n",
    "                    for i2 in range(i+1,r):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[p][i][j] = (dp[p][i][j] + dp[p-1][i2][j])%MOD\n",
    "                    for j2 in range(j+1,c):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[p][i][j] = (dp[p][i][j] + dp[p-1][i][j2])%MOD\n",
    "                    if p==k: break\n",
    "                if p==k: break\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], K: int) -> int:\n",
    "        n,m = len(pizza),len(pizza[0])\n",
    "        app = [[0]*m for _ in range(n)]\n",
    "        if pizza[n-1][m-1] == 'A':\n",
    "            app[n-1][m-1] = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            app[i][m-1] = app[i+1][m-1] + int(pizza[i][m-1] == 'A')\n",
    "        for j in range(m-2,-1,-1):\n",
    "            app[n-1][j] = app[n-1][j+1] + int(pizza[n-1][j] == 'A')\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(m-2,-1,-1):\n",
    "                app[i][j] = app[i+1][j] + app[i][j+1] - app[i+1][j+1] + int(pizza[i][j] == 'A')\n",
    "        dp = [[[0]*m for _ in range(n)] for _ in range(K+1)]\n",
    "        for i in range(n):\n",
    "            #print(app[i])\n",
    "            for j in range(m):\n",
    "                if app[i][j]>0:\n",
    "                    dp[1][i][j] = 1\n",
    "                else:\n",
    "                    dp[1][i][j] = 0\n",
    "        Mod = 10**9+7\n",
    "        for k in range(2,K+1):\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    #水平\n",
    "                    for i2 in range(i+1,n):\n",
    "                        if app[i][j] > app[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k-1][i2][j]+dp[k][i][j])%Mod\n",
    "                    for j2 in range(j+1,m):\n",
    "                        if app[i][j] > app[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j]+dp[k-1][i][j2])%Mod\n",
    "        return dp[K][0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10**9+7\n",
    "        apple = [[0] * (n+1) for _ in range(m+1)]\n",
    "        # dp[k][i][j] = [i,j]位置右下角分割成k块的方案数\n",
    "        dp = [ [[0 for _ in range(n)] for _ in range(m)] for _ in range(k+1) ]\n",
    "        print(len(dp), len(dp[0]), len(dp[0][0]))\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if pizza[i][j] == 'A':\n",
    "                    apple[i][j] = apple[i+1][j]+apple[i][j+1]-apple[i+1][j+1]+1\n",
    "                    dp[1][i][j] = 1 if apple[i][j] > 0 else 0\n",
    "                else:\n",
    "                    apple[i][j] = apple[i+1][j]+apple[i][j+1]-apple[i+1][j+1]\n",
    "                    dp[1][i][j] = 1 if apple[i][j] > 0 else 0\n",
    "        for ki in range(1, k+1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for i2 in range(i+1, m):\n",
    "                        # confuse\n",
    "                        if apple[i][j] > apple[i2][j]:\n",
    "                            dp[ki][i][j] = (dp[ki][i][j]+dp[ki-1][i2][j]) % mod\n",
    "                    for j2 in range(j+1, n):\n",
    "                        if apple[i][j] > apple[i][j2]:\n",
    "                            dp[ki][i][j] = (dp[ki][i][j]+dp[ki-1][i][j2]) % mod\n",
    "\n",
    "        return dp[k][0][0]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        r,c=len(pizza),len(pizza[0])\n",
    "        apples = [[0]*(c+1) for _ in range(r+1)]\n",
    "        dp = [[[0]*c for _ in range(r)] for _ in range(k+1)]\n",
    "\n",
    "        for i in range(r-1,-1,-1):\n",
    "            for j in range(c-1,-1,-1):\n",
    "                apples[i][j] = apples[i+1][j] + apples[i][j+1] - \\\n",
    "                    apples[i+1][j+1] + (pizza[i][j]=='A')\n",
    "                dp[1][i][j] = 1 if apples[i][j]>0 else 0\n",
    "\n",
    "        for p in range(1,k+1):\n",
    "            for i in range(r):\n",
    "                for j in range(c):\n",
    "                    for i2 in range(i+1,r):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[p][i][j] = (dp[p][i][j] + dp[p-1][i2][j])%MOD\n",
    "                    for j2 in range(j+1,c):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[p][i][j] = (dp[p][i][j] + dp[p-1][i][j2])%MOD\n",
    "                    # if p==k: break\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        ms = matrixsum(pizza)\n",
    "        n=len(pizza)\n",
    "        m=len(pizza[0])\n",
    "        f=[[[0]*(m+1) for _ in range(n+1)] for _ in range(k)]\n",
    "        for c in range(k):\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    if c==0:\n",
    "                        if ms.query(i,j,n,m):\n",
    "                            f[0][i][j]=1\n",
    "                            continue\n",
    "                    res=0\n",
    "                    for j2 in range(j+1,m):\n",
    "                        if ms.query(i,j,n,j2):\n",
    "                            res+=f[c-1][i][j2]\n",
    "                    for i2 in range(i+1,n):\n",
    "                        if ms.query(i,j,i2,m):\n",
    "                            res+=f[c-1][i2][j]\n",
    "                    f[c][i][j]=res%mod\n",
    "        return f[-1][0][0]\n",
    "\n",
    "\n",
    "class matrixsum:\n",
    "    def __init__(self,matrix):\n",
    "        n,m=len(matrix),len(matrix[0])\n",
    "        s=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+(matrix[i][j]=='A')\n",
    "        self.s=s\n",
    "    def query(self,r1,c1,r2,c2):\n",
    "        return self.s[r2][c2]-self.s[r1][c2]-self.s[r2][c1]+self.s[r1][c1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # 横切dp[i-1][j] + dp[i-2][j] + ... + dp[0][j]\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        sufsum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        dp = [[[0 for _ in range(k+1)] for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                sufsum[i][j] = sufsum[i][j+1] + sufsum[i+1][j] - sufsum[i+1][j+1] + (pizza[i][j] == \"A\")\n",
    "                dp[i][j][1] = 1 if sufsum[i][j] > 0 else 0\n",
    "        for w in range(2, k+1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for i2 in range(i+1, m):\n",
    "                        # (i, j) (t-1, n-1)\n",
    "                        if sufsum[i][j] > sufsum[i2][j]:\n",
    "                            dp[i][j][w] = (dp[i][j][w] + dp[i2][j][w-1]) % (10**9+7)\n",
    "                    for j2 in range(j+1, n):\n",
    "                        # (i, j) (m-1, t-1)\n",
    "                        if sufsum[i][j] > sufsum[i][j2]:\n",
    "                            dp[i][j][w] = (dp[i][j][w] + dp[i][j2][w-1]) % (10**9+7)\n",
    "        return dp[0][0][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m = len(pizza)\n",
    "        n = len(pizza[0])\n",
    "        mod = 10**9+7\n",
    "        apples = [[0] * (n+1)  for _ in range(m+1)]\n",
    "        dp = [[[0] * n  for _ in range(m)] for _ in range(k)]\n",
    "        res = 0\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                apples[i][j] = apples[i][j+1] + apples[i+1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[0][i][j] = 1 if apples[i][j] > 0 else 0\n",
    "        for time in range(1, k):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    for i1 in range(i+1, m):\n",
    "                        if apples[i][j] > apples[i1][j] and apples[i1][j] > 0:\n",
    "                            dp[time][i][j] += dp[time-1][i1][j]\n",
    "                    for j1 in range(j+1, n):\n",
    "                        if apples[i][j] > apples[i][j1] and apples[i][j1] > 0:\n",
    "                            dp[time][i][j] += dp[time-1][i][j1]\n",
    "        return dp[k-1][0][0] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ms = MatrixSum(pizza)\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        f = [[[0] * n for _ in range(m)] for _ in range(k)]\n",
    "        # 把递归代码 1:1 翻译成递推\n",
    "        for c in range(k):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if c == 0:\n",
    "                        f[c][i][j] = 1 if ms.query(i, j, m, n) else 0\n",
    "                        continue\n",
    "                    res = 0\n",
    "                    for j2 in range(j + 1, n):  # 垂直切\n",
    "                        if ms.query(i, j, m, j2):  # 有苹果\n",
    "                            res += f[c - 1][i][j2]\n",
    "                    for i2 in range(i + 1, m):  # 水平切\n",
    "                        if ms.query(i, j, i2, n):  # 有苹果\n",
    "                            res += f[c - 1][i2][j]\n",
    "                    f[c][i][j] = res % MOD\n",
    "        return f[-1][0][0]\n",
    "\n",
    "# 二维前缀和模板（'A' 视作 1，'.' 视作 0）\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[str]):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + (x == 'A')\n",
    "        self.s = s\n",
    "\n",
    "    # 返回左上角在 (r1,c1) 右下角在 (r2-1,c2-1) 的子矩阵元素和（类似前缀和的左闭右开）\n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j]  = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(2, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "        return dp[k][0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        from copy import deepcopy\n",
    "        mod = int(1e9+7)\n",
    "        n,m = len(pizza), len(pizza[0])\n",
    "        dp = [[[0]*(k+2) for _ in range(m)]for _ in range(n)]\n",
    "        cnt = [[0]*(m+1) for _ in range(n+1)]\n",
    "        for p in range(n):\n",
    "            for q in range(m):\n",
    "                if pizza[p][q] == 'A':\n",
    "                    cnt[p+1][q+1] = 1\n",
    "                cnt[p+1][q+1] += cnt[p+1][q]\n",
    "        for p in range(1,n+1):\n",
    "            for q in range(m+1):\n",
    "                cnt[p][q] += cnt[p-1][q]\n",
    "        \n",
    "        def has(p1,p2,q1,q2):\n",
    "            return abs(cnt[p1][q1]+cnt[p2][q2]-cnt[p1][q2]-cnt[p2][q1])\n",
    "        \n",
    "        def deal(p,q):\n",
    "            tot = has(n,p,m,q)\n",
    "            if tot:\n",
    "                dp[p][q][1] = 1\n",
    "            else:\n",
    "                return\n",
    "            for sp in range(n-1,p,-1):\n",
    "                split = has(sp,p,m,q)\n",
    "                if not split:\n",
    "                    break\n",
    "                rest = min(k,tot-split)\n",
    "                for r in range(1,rest+1):\n",
    "                    dp[p][q][r+1] += dp[sp][q][r]\n",
    "            for sq in range(m-1,q,-1):\n",
    "                split = has(n,p,sq,q)\n",
    "                if not split:\n",
    "                    break\n",
    "                rest = min(k,tot-split)\n",
    "                for r in range(1,rest+1):\n",
    "                    dp[p][q][r+1] += dp[p][sq][r]\n",
    "            for r in range(1,k+1):\n",
    "                dp[p][q][k] %= mod\n",
    "        \n",
    "        for p in range(n-1,-1,-1):\n",
    "            for q in range(m-1,-1,-1):\n",
    "                deal(p,q)\n",
    "        return dp[0][0][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j]  = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(2, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "        return dp[k][0][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        def check(rl: int, rr: int, cl: int, cr: int) -> bool:\n",
    "            for x in range(rl, rr):\n",
    "                for y in range(cl, cr):\n",
    "                    if pizza[x][y] == 'A':\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                dp[row][col][0] = int(check(row, m, col, n))\n",
    "        for row in range(m - 1, -1, -1):\n",
    "            for col in range(n - 1, -1, -1):\n",
    "                for cnt in range(1, k):\n",
    "                    res = 0\n",
    "                    for i in range(m - 1, row, -1):\n",
    "                        if check(row, i, col, n):\n",
    "                            res += dp[i][col][cnt - 1]\n",
    "                            res %= MOD\n",
    "                    for j in range(n - 1, col, -1):\n",
    "                        if check(row, m, col, j):\n",
    "                            res += dp[row][j][cnt - 1]\n",
    "                            res %= MOD\n",
    "                    dp[row][col][cnt] = res\n",
    "        return dp[0][0][k - 1]\n",
    "\n",
    "        @cache\n",
    "        def dfs(row: int, col: int, cnt: int) -> int:\n",
    "            if cnt == 0:\n",
    "                return int(check(row, m, col, n))\n",
    "            res = 0\n",
    "            for i in range(row + 1, m):\n",
    "                if check(row, i, col, n):\n",
    "                    res += dfs(i, col, cnt - 1)\n",
    "                    res %= MOD\n",
    "            for j in range(col + 1, n):\n",
    "                if check(row, m, col, j):\n",
    "                    res += dfs(row, j, cnt - 1)\n",
    "                    res %= MOD\n",
    "            return res\n",
    "        return dfs(0, 0, k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 1000000007\n",
    "        pizzaArray = [[0 for _ in range(len(pizza[0]) + 1)] for _ in range(len(pizza) + 1)]\n",
    "        for i in range(len(pizza) - 1, -1, -1):\n",
    "            for j in range(len(pizza[0]) - 1, -1, -1):\n",
    "                pizzaArray[i][j] = (pizza[i][j] == 'A') + pizzaArray[i + 1][j] + pizzaArray[i][j + 1] - \\\n",
    "                                   pizzaArray[i + 1][\n",
    "                                       j + 1]\n",
    "\n",
    "        dp = [[[0 for _ in range(len(pizza[0]) + 1)] for _ in range(len(pizza) + 1)] for _ in range(k + 1)]\n",
    "\n",
    "        for i in range(len(pizza) - 1, -1, -1):\n",
    "            for j in range(len(pizza[0]) - 1, -1, -1):\n",
    "                dp[0][i][j] = 1 if pizzaArray[i][j] > 0 else 0\n",
    "\n",
    "        for c in range(k + 1):\n",
    "            for i in range(len(pizza) - 1, -1, -1):\n",
    "                for j in range(len(pizza[0]) - 1, -1, -1):\n",
    "                    # 竖着切\n",
    "                    for j1 in range(j + 1, len(pizza[0])):\n",
    "                        if pizzaArray[i][j] > pizzaArray[i][j1] > 0:\n",
    "                            dp[c][i][j] += dp[c - 1][i][j1]\n",
    "                            dp[c][i][j] = dp[c][i][j] % MOD\n",
    "\n",
    "                    # 横着切\n",
    "                    for i1 in range(i + 1, len(pizza)):\n",
    "                        if pizzaArray[i][j] > pizzaArray[i1][j] > 0:\n",
    "                            dp[c][i][j] += dp[c - 1][i1][j]\n",
    "                            dp[c][i][j] = dp[c][i][j] % MOD\n",
    "        return dp[k - 1][0][0]\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod7 = 1e9+7\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza, k: int) -> int:\n",
    "        arr = [[c == 'A' for c in row] for row in pizza]\n",
    "        #for row in arr:\n",
    "        #    print(''.join(['@' if v else ' ' for v in row]))\n",
    "\n",
    "        n, m = len(arr), len(arr[0])\n",
    "\n",
    "        # has row\n",
    "        hasrow = [[False] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            hasrow[i][-1] = arr[i][-1]\n",
    "            for j in range(m-2, -1, -1):\n",
    "                hasrow[i][j] = arr[i][j] or hasrow[i][j + 1]\n",
    "        \n",
    "        # has col\n",
    "        hascol = [[False] * m for _ in range(n)]\n",
    "        hascol[-1] = arr[-1]\n",
    "        for j in range(m):\n",
    "            for i in range(n-2, -1, -1):\n",
    "                hascol[i][j] = arr[i][j] or hascol[i + 1][j]\n",
    "        \n",
    "        # has\n",
    "        has = [[False] * m for _ in range(n)]\n",
    "        has[-1] = hasrow[-1]\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            has[i][-1] = hascol[i][-1]\n",
    "            for j in range(m-2, -1, -1):\n",
    "                has[i][j] = arr[i][j] or has[i + 1][j] or has[i][j + 1]\n",
    "        \n",
    "        # cache\n",
    "        cache = [[[-1] * k for _ in range(m)] for _ in range(n)]\n",
    "        \n",
    "        def calc(row, col, k):\n",
    "            if k == 0:\n",
    "                return 1 if has[row][col] else 0\n",
    "            \n",
    "            if k < 0 or k + 1 >= m + n - row - col:\n",
    "                return 0\n",
    "            \n",
    "            #print(row, col, k)\n",
    "            if cache[row][col][k] >= 0:\n",
    "                return cache[row][col][k]\n",
    "\n",
    "            cnt = 0\n",
    "            hit = False\n",
    "            for i in range(row, n-1):\n",
    "                if hit or hasrow[i][col]:\n",
    "                    hit = True\n",
    "                    cnt = (cnt + calc(i+1, col, k-1)) % mod7\n",
    "            \n",
    "            hit = False\n",
    "            for j in range(col, m-1):\n",
    "                if hit or hascol[row][j]:\n",
    "                    hit = True\n",
    "                    cnt = (cnt + calc(row, j+1, k-1)) % mod7\n",
    "            \n",
    "            cache[row][col][k] = cnt\n",
    "            return int(cnt)\n",
    "\n",
    "        return calc(0, 0, k-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        ps = [[0]*(n+1) for _ in range(1+m)]\n",
    "        for i in range(1, 1+m):\n",
    "            for j in range(1, 1+n):\n",
    "                ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + int(pizza[i-1][j-1] == 'A')\n",
    "        \n",
    "        print(ps)\n",
    "        dp = [[[0]*k for _ in range(n)] for i in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                dp[i][j][0] = int(ps[m][n] - ps[m][j] - ps[i][n] + ps[i][j] > 0)\n",
    "                for p in range(1, k):\n",
    "                    # 水平切割\n",
    "                    for i1 in range(i+1, m):\n",
    "                        tmp = ps[i1][n] - ps[i1][j] - ps[i][n] + ps[i][j]\n",
    "                        if tmp > 0:\n",
    "                            dp[i][j][p] += dp[i1][j][p-1]\n",
    "                    # 垂直切割\n",
    "                    for j1 in range(j+1, n):\n",
    "                        tmp = ps[m][j1] - ps[m][j] - ps[i][j1] + ps[i][j]\n",
    "                        if tmp > 0:\n",
    "                            dp[i][j][p] += dp[i][j1][p-1]\n",
    "                    dp[i][j][p] %= mod\n",
    "                # print((i, j), dp)\n",
    "        return dp[0][0][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # dp[i][j] 表示 i,j --> n-1, m-1 的矩阵切切切的方案数量 （0<=i<n, 0 <= j < m）\n",
    "        # dp[i][j] = \n",
    "        #     sum(dp[i+k][j] for k=0...m-1-i if i,j ~ i+k,j 之间有苹果) + \n",
    "        #     sum(dp[i][j+k] for k=0...n-1-j if i,j ~ i,j+k 之间有苹果)\n",
    "        # ans: dp[i][j] i,j n,m里没苹果：1\n",
    "\n",
    "        n, m, mod = len(pizza), len(pizza[0]), int(1e9+7)\n",
    "        apple = [ [0 for _ in range(m)] for _ in range(n) ]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                apple[i][j] = ( 0\n",
    "                    + (apple[i-1][j] if i > 0 else 0)\n",
    "                    + (apple[i][j-1] if j > 0 else 0)\n",
    "                    - (apple[i-1][j-1] if i > 0 and j > 0 else 0)\n",
    "                    + (pizza[i][j] == 'A')\n",
    "                )\n",
    "        \n",
    "        def has_apple(i1, j1, i2, j2):\n",
    "            \"\"\" (i1, j1) ... (i2, j2) 是否包含苹果 \"\"\"\n",
    "            return ( 0\n",
    "                + apple[i2][j2] \n",
    "                - (apple[i2][j1-1] if j1 > 0 else 0)\n",
    "                - (apple[i1-1][j2] if i1 > 0 else 0)\n",
    "                + (apple[i1-1][j1-1] if i1 > 0 and j1 > 0 else 0)\n",
    "            ) > 0\n",
    "        \n",
    "        dp = [\n",
    "            [\n",
    "                [\n",
    "                    0 \n",
    "                    for _ in range(m)\n",
    "                ]\n",
    "                for _ in range(n)\n",
    "            ]\n",
    "            for _ in range(k)\n",
    "        ]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if has_apple(i, j, n-1, m-1):\n",
    "                    dp[0][i][j] = 1\n",
    "\n",
    "        for kk in range(1, k):\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    for ii in range(i+1, n):\n",
    "                        if has_apple(i, j, ii-1, m-1):\n",
    "                            dp[kk][i][j] = (dp[kk][i][j] + dp[kk-1][ii][j])%mod\n",
    "                    for jj in range(j+1, m):\n",
    "                        if has_apple(i, j, n-1, jj-1):\n",
    "                            dp[kk][i][j] = (dp[kk][i][j] + dp[kk-1][i][jj])%mod\n",
    "        for kk in range(k):\n",
    "            print('---', kk)\n",
    "            for ii in range(n):\n",
    "                for jj in range(m):\n",
    "                    print(dp[kk][ii][jj], end=' ')\n",
    "                print()\n",
    "\n",
    "        return dp[k-1][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n, mod = len(pizza), len(pizza[0]), 10 ** 9 + 7\n",
    "        apples = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        dp = [[[0 for j in range(n)] for i in range(m)] for _ in range(k + 1)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                apples[i][j] = apples[i][j + 1] + apples[i + 1][j] - apples[i + 1][j + 1] + (pizza[i][j] == 'A')\n",
    "                dp[1][i][j] = 1 if apples[i][j] > 0 else 0\n",
    "\n",
    "        for k in range(1, k + 1):\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    # 水平方向切\n",
    "                    for i2 in range(i + 1, m):\n",
    "                        if apples[i][j] > apples[i2][j]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i2][j]) % mod\n",
    "                    # 垂直方向切\n",
    "                    for j2 in range(j + 1, n):\n",
    "                        if apples[i][j] > apples[i][j2]:\n",
    "                            dp[k][i][j] = (dp[k][i][j] + dp[k - 1][i][j2]) % mod\n",
    "            print(dp[k])\n",
    "        return dp[k][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        ps = [[0]*(n+1) for _ in range(1+m)]\n",
    "        for i in range(1, 1+m):\n",
    "            for j in range(1, 1+n):\n",
    "                ps[i][j] = ps[i-1][j] + ps[i][j-1] - ps[i-1][j-1] + int(pizza[i-1][j-1] == 'A')\n",
    "        \n",
    "        print(ps)\n",
    "        dp = [[[0]*k for _ in range(n)] for i in range(m)]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n-1, -1, -1):\n",
    "                dp[i][j][0] = int(ps[m][n] - ps[m][j] - ps[i][n] + ps[i][j] > 0)\n",
    "                for p in range(1, k):\n",
    "                    # 水平切割\n",
    "                    for i1 in range(i+1, m):\n",
    "                        tmp = ps[i1][n] - ps[i1][j] - ps[i][n] + ps[i][j]\n",
    "                        if tmp > 0:\n",
    "                            dp[i][j][p] += dp[i1][j][p-1]\n",
    "                    # 垂直切割\n",
    "                    for j1 in range(j+1, n):\n",
    "                        tmp = ps[m][j1] - ps[m][j] - ps[i][j1] + ps[i][j]\n",
    "                        if tmp > 0:\n",
    "                            dp[i][j][p] += dp[i][j1][p-1]\n",
    "                    dp[i][j][p] %= mod\n",
    "                # print((i, j), dp)\n",
    "        return dp[0][0][-1]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        ### https: // zhuanlan.zhihu.com / p / 139694223\n",
    "        row = len(pizza)\n",
    "        col = len(pizza[0])\n",
    "        dp_apple = [[0 for _ in range(col)] for _ in range(row)]  # 存放以（i,j）为左上角，（row-1,col-1）为右下角的矩形块中的苹果数\n",
    "        for i in range(row - 1, -1, -1):  # 使用动态规划，二维前缀和完成这个过程\n",
    "            for j in range(col - 1, -1, -1):\n",
    "                if i == row - 1 and j == col - 1:\n",
    "                    dp_apple[i][j] = 1 if pizza[i][j] == 'A' else 0\n",
    "                elif i == row - 1:\n",
    "                    dp_apple[i][j] = dp_apple[i][j + 1] + 1 if pizza[i][j] == 'A' else dp_apple[i][j + 1]\n",
    "                elif j == col - 1:\n",
    "                    dp_apple[i][j] = dp_apple[i + 1][j] + 1 if pizza[i][j] == 'A' else dp_apple[i + 1][j]\n",
    "                else:\n",
    "                    dp_apple[i][j] = dp_apple[i + 1][j] + dp_apple[i][j + 1] - dp_apple[i + 1][j + 1]\n",
    "                    dp_apple[i][j] += 1 if pizza[i][j] == 'A' else 0\n",
    "\n",
    "        dp = [[[-1 for _ in range(k + 1)] for _ in range(col)] for _ in range(row)]\n",
    "\n",
    "        # dp[i][j][k]表示，（i，j）为左上角的披萨，分成k份的方案数\n",
    "        def dfs(x, y, z):\n",
    "            apple = dp_apple[x][y]  # 以（x,y）为左上角的矩形的苹果数\n",
    "            if dp[x][y][z] != -1:  # 备忘录，如果之前计算过，直接返回\n",
    "                return dp[x][y][z]\n",
    "            if apple < z:  # 苹果数不够，返回0\n",
    "                return 0\n",
    "            if z == 1:  # 分成一块，不需要切，直接返回1\n",
    "                return 1\n",
    "            dp[x][y][z] = 0  # 计算\n",
    "            for i in range(x + 1, row):  # 横向切\n",
    "                if dp_apple[i][y] < apple:  # 切下来的有苹果才行\n",
    "                    dp[x][y][z] += dfs(i, y, z - 1)  # dfs\n",
    "            for i in range(y + 1, col):  # 竖着切\n",
    "                if dp_apple[x][i] < apple:  # 切下来的有苹果才行\n",
    "                    dp[x][y][z] += dfs(x, i, z - 1)  # dfs\n",
    "            return dp[x][y][z] % (10 ** 9 + 7)  # 结果求模\n",
    "\n",
    "        return dfs(0, 0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        row = len(pizza)\n",
    "        col = len(pizza[0])\n",
    "        dp_apple = [[0 for _ in range(col)] for _ in range(row)]#存放以（i,j）为左上角，（row-1,col-1）为右下角的矩形块中的苹果数\n",
    "        for i in range(row-1,-1,-1): #使用动态规划，二维前缀和完成这个过程\n",
    "            for j in range(col-1,-1,-1):\n",
    "                if i == row-1 and j == col-1:\n",
    "                    dp_apple[i][j] = 1 if pizza[i][j] == 'A' else 0\n",
    "                elif i == row-1:\n",
    "                    dp_apple[i][j] = dp_apple[i][j+1] + 1 if pizza[i][j] == 'A' else dp_apple[i][j+1]\n",
    "                elif j == col-1:\n",
    "                    dp_apple[i][j] = dp_apple[i+1][j] + 1 if pizza[i][j] == 'A' else dp_apple[i+1][j]\n",
    "                else:\n",
    "                    dp_apple[i][j] = dp_apple[i+1][j] + dp_apple[i][j+1] - dp_apple[i+1][j+1]\n",
    "                    dp_apple[i][j] += 1 if pizza[i][j] == 'A' else 0\n",
    "        \n",
    "        dp = [[[-1 for _ in range(k+1)] for _ in range(col) ]for _ in range(row)] \n",
    "        #dp[i][j][k]表示，（i，j）为左上角的披萨，分成k份的方案数\n",
    "        def dfs(x,y,z):\n",
    "            apple = dp_apple[x][y] #以（x,y）为左上角的矩形的苹果数\n",
    "            if dp[x][y][z] != -1: #备忘录，如果之前计算过，直接返回\n",
    "                return dp[x][y][z]\n",
    "            if apple < z: #苹果数不够，返回0\n",
    "                return 0\n",
    "            if z == 1: #分成一块，不需要切，直接返回1\n",
    "                return 1\n",
    "            dp[x][y][z] = 0 #计算\n",
    "            for i in range(x+1,row): #横向切\n",
    "                if dp_apple[i][y] < apple: #切下来的有苹果才行\n",
    "                    dp[x][y][z] += dfs(i,y,z-1) #dfs\n",
    "            for i in range(y+1,col): #竖着切\n",
    "                if dp_apple[x][i] < apple: #切下来的有苹果才行\n",
    "                    dp[x][y][z] += dfs(x,i,z-1) #dfs\n",
    "            return dp[x][y][z] % (10**9+7) #结果求模       \n",
    "        return dfs(0,0,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        row, col = len(pizza), len(pizza[0])\n",
    "        presum = [[0 for c in range(col)] for r in range(row)]\n",
    "        # if pizza[0][0] == 'A': presum[0][0] = 1\n",
    "        # for i in range(1, row): presum[i][0] = presum[i-1][0] + (pizza[i][0] == 'A')\n",
    "        # for j in range(1, col): presum[0][j] = presum[0][j-1] + (pizza[0][j] == 'A')\n",
    "        # for i in range(1, row):\n",
    "        #     for j in range(1, col):\n",
    "        #         presum[i][j] = presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1] + (pizza[i][j] == 'A')\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                presum[i][j] += presum[i-1][j] if i > 0 else 0\n",
    "                presum[i][j] += presum[i][j-1] if j > 0 else 0\n",
    "                presum[i][j] -= presum[i-1][j-1] if i > 0 and j > 0 else 0\n",
    "                if pizza[i][j] == 'A':\n",
    "                     presum[i][j] += 1\n",
    "        # print(presum)\n",
    "\n",
    "        def hasApple(i, j, x, y):\n",
    "            num1, num2, num3 = 0, 0, 0\n",
    "            if i != 0 and j != 0: num1 = presum[i-1][j-1]\n",
    "            if i != 0: num2 = presum[i-1][y]\n",
    "            if j != 0: num3 = presum[x][j-1]\n",
    "            return presum[x][y] - num2 - num3 + num1 > 0\n",
    "\n",
    "        dp = [[[0 for _ in range(k+1)] for c in range(col)] for r in range(row)]\n",
    "        dp[0][0][1] = 1\n",
    "        if presum[row-1][col-1] == 0: return 0\n",
    "        \n",
    "        for x in range(2, k+1):\n",
    "            for i in range(row):\n",
    "                for j in range(col):\n",
    "                    if dp[i][j][x-1] == 0: continue\n",
    "\n",
    "                    for z in range(i+1,row):\n",
    "                        if hasApple(i, j, z-1, col-1) and hasApple(z, j, row-1, col-1):\n",
    "                            dp[z][j][x] += dp[i][j][x-1]\n",
    "                            dp[z][j][x] %= MOD\n",
    "                    for z in range(j+1, col):\n",
    "                        if hasApple(i, j, row-1, z-1) and hasApple(i, z, row-1, col-1):\n",
    "                            dp[i][z][x] += dp[i][j][x-1]\n",
    "                            dp[i][z][x] %= MOD\n",
    "        print(dp)\n",
    "        ans = 0\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                ans += dp[i][j][k]\n",
    "                ans %= MOD\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 1_000_000_007\n",
    "        yLen, xLen = len(pizza), len(pizza[0])\n",
    "        \n",
    "        @cache\n",
    "        def dp(curY: int, curX: int) -> List[int]:\n",
    "            if curY == yLen or curX == xLen: return None\n",
    "            \n",
    "            xHasApple = yHasApple = False\n",
    "\n",
    "            for y in range(curY, yLen):\n",
    "                if pizza[y][curX] == 'A':\n",
    "                    yHasApple = True\n",
    "                    break\n",
    "            \n",
    "            for x in range(curX, xLen):\n",
    "                if pizza[curY][x] == 'A':\n",
    "                    xHasApple = True\n",
    "                    break\n",
    "            \n",
    "            if xHasApple == yHasApple == False:\n",
    "                return dp(curY + 1, curX + 1)\n",
    "\n",
    "            if yHasApple == False:\n",
    "                return dp(curY, curX + 1)\n",
    "\n",
    "            if xHasApple == False:\n",
    "                return dp(curY + 1, curX)\n",
    "\n",
    "            res = [0] * (k + 1)\n",
    "\n",
    "            for y in range(curY + 1, yLen):\n",
    "                li = dp(y, curX)\n",
    "                if li == None: continue\n",
    "                for i in range(0, k): res[i + 1] += li[i]\n",
    "            \n",
    "            for x in range(curX + 1, xLen):\n",
    "                li = dp(curY, x)\n",
    "                if li == None: continue\n",
    "                for i in range(0, k): res[i + 1] += li[i]\n",
    "            \n",
    "            res[0] = 1\n",
    "            \n",
    "            return res\n",
    "\n",
    "        ans = dp(0, 0)\n",
    "\n",
    "        return ans[k - 1] % MOD if ans else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "状态:\n",
    "f[i][j][k] 代表从格子(i,j) -> 格子(m-1, n-1)划分k块披萨有多少种方案\n",
    "# 枚举竖直切片\n",
    "# 枚举水平切片\n",
    "ans: f[0][0][k]\n",
    "'''\n",
    "class P:\n",
    "\n",
    "    def __init__(self, A: List[List[int]]):\n",
    "        m,n = len(A), len(A[0])\n",
    "        preSum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + int(A[i - 1][j - 1] == \"A\")\n",
    "        self.preSum = preSum\n",
    "\n",
    "    def get(self, x1: int, y1: int, x2: int, y2: int) -> int:\n",
    "        A = self.preSum\n",
    "        return A[x2 + 1][y2 + 1] - A[x1][y2 + 1] - A[x2 + 1][y1] + A[x1][y1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, a: List[str], k: int) -> int:\n",
    "        m,n = len(a), len(a[0])\n",
    "        s = P(a)\n",
    "        M = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i:int, j:int, remain: int) -> int:\n",
    "            if remain == 1:\n",
    "                # print(s.get(i, j, m-1, n-1))\n",
    "                if s.get(i, j, m-1, n-1) >= 1:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            # 枚举水平切割点\n",
    "            ans = 0\n",
    "            \n",
    "            for x in range(i+1, m):\n",
    "                if s.get(i, j, x-1, n-1) > 0 and s.get(x, j, m-1, n-1) > 0:\n",
    "                    ans += dfs(x, j, remain - 1) % M\n",
    "            \n",
    "            for y in range(j+1,n):\n",
    "                if s.get(i, j, m-1, y-1) > 0 and s.get(i, y, m-1, n-1) > 0 :\n",
    "                    ans += dfs(i, y, remain - 1) % M\n",
    "            return ans % M\n",
    "        \n",
    "        return dfs(0, 0, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        rows, cols = len(pizza), len(pizza[0])\n",
    "\n",
    "        @cache\n",
    "        def apples(row: int, col: int) -> int:\n",
    "            return (pizza[row][col] == 'A') + apples(row, col + 1) + apples(row + 1, col) - apples(row + 1, col + 1) \\\n",
    "                if row < rows and col < cols else 0\n",
    "\n",
    "        @cache\n",
    "        def dp(row: int, col: int, num: int) -> int:\n",
    "            if rows - row + cols - col - 1 < num:\n",
    "                return 0\n",
    "            if num == 1:\n",
    "                return int(apples(row, col) > 0)\n",
    "            return (sum(dp(i, col, num - 1) for i in range(row + 1, rows) if apples(row, col) - apples(i, col) > 0) +\n",
    "                    sum(dp(row, j, num - 1) for j in range(col + 1, cols) if apples(row, col) - apples(row, j) > 0)) \\\n",
    "                % 1000000007\n",
    "\n",
    "        return dp(0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: list[str], k: int) -> int:\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        maps = defaultdict(list)\n",
    "        for x in range(m):\n",
    "            maps[(x, n)].append((x, n))\n",
    "            maps[(x, n)].append((x, n))\n",
    "        for y in range(n):\n",
    "            maps[(m, y)].append((m, y))\n",
    "            maps[(m, y)].append((m, y))\n",
    "        suffix = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                suffix[i][j] = suffix[i + 1][j]+suffix[i][j+1]-suffix[i+1][j+1] + int(pizza[i][j] == 'A')\n",
    "                if suffix[i][j] > suffix[i + 1][j]:\n",
    "                    maps[(i, j)].append((i + 1, j))\n",
    "                else:\n",
    "                    maps[(i, j)].append(maps[(i + 1, j)][0])\n",
    "                if suffix[i][j] > suffix[i][j + 1]:\n",
    "                    maps[(i, j)].append((i, j + 1))\n",
    "                else:\n",
    "                    maps[(i, j)].append(maps[(i, j + 1)][1])\n",
    "\n",
    "        dp = [[int(bool(suffix[i][j] > 0)) for j in range(n + 1)] for i in range(m + 1)]\n",
    "        row = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        col = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        for _ in range(k - 1):\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    row[i][j] = row[i][j + 1] + dp[i][j]\n",
    "                    row[i][j] %= MOD\n",
    "                    col[i][j] = col[i + 1][j] + dp[i][j]\n",
    "                    col[i][j] %= MOD\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    dp[i][j] = 0\n",
    "                    x, y = maps[(i, j)][1]\n",
    "                    dp[i][j] += row[x][y]\n",
    "                    x, y = maps[(i, j)][0]\n",
    "                    dp[i][j] += col[x][y]\n",
    "                    dp[i][j] %= MOD\n",
    "\n",
    "        return dp[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # init\n",
    "        m,n = len(pizza),len(pizza[0])\n",
    "        col_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        row_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        rhave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        chave = [[False]*(n+1) for _ in range(m+1)]\n",
    "\n",
    "        for x in range(m-1,-1,-1):\n",
    "            for y in range(n-1,-1,-1):\n",
    "                # column\n",
    "                chave[x][y] = chave[x+1][y] or pizza[x][y]==\"A\"\n",
    "                if not chave[x][y]:\n",
    "                    col_first[x][y] = col_first[x][y+1].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        for yright in range(y+1,n):\n",
    "                            col_first[x][y][i] += dp[x][yright][i-1]\n",
    "                    col_first[x][y][0] = 1\n",
    "                # row\n",
    "                rhave[x][y] = rhave[x][y+1] or pizza[x][y]==\"A\"\n",
    "                if not rhave[x][y]:\n",
    "                    row_first[x][y] = row_first[x+1][y].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        for xdown in range(x+1,m):\n",
    "                            row_first[x][y][i] += dp[xdown][y][i-1]\n",
    "                    row_first[x][y][0] = 1\n",
    "                # dp\n",
    "                for i in range(k):\n",
    "                    dp[x][y][i] = col_first[x][y][i] + row_first[x][y][i]\n",
    "                dp[x][y][0] = min(1,dp[x][y][0])\n",
    "        return mod(dp[0][0][-1],10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # init\n",
    "        m,n = len(pizza),len(pizza[0])\n",
    "        col_first = [[0]*k for _ in range(n+1)]\n",
    "        row_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        rsum = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        csum = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        rhave = [False]*(n+1)\n",
    "        chave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        # dp\n",
    "        for x in range(m-1,-1,-1):\n",
    "            for y in range(n-1,-1,-1):\n",
    "                # cut column first\n",
    "                chave[x][y] = chave[x+1][y] or pizza[x][y]==\"A\"\n",
    "                if not chave[x][y]:\n",
    "                    col_first[y] = col_first[y+1].copy()\n",
    "                else: # 这一列有\"A\"\n",
    "                    col_first[y] = [0]*k # 清零\n",
    "                    for i in range(1,k):\n",
    "                        col_first[y][i] += csum[x][y+1][i-1] # 累加 竖切第一刀后, 剩余部份的方法数\n",
    "                    col_first[y][0] = 1\n",
    "                # cut row first\n",
    "                rhave[y] = rhave[y+1] or pizza[x][y]==\"A\"\n",
    "                if not rhave[y]:\n",
    "                    row_first[x][y] = row_first[x+1][y].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        row_first[x][y][i] += rsum[x+1][y][i-1]\n",
    "                    row_first[x][y][0] = 1\n",
    "                # update dp\n",
    "                cur_result = [0]*k # result for current sub-pizza: pizza[x:m][y:n]\n",
    "                for i in range(k):\n",
    "                    cur_result[i] = col_first[y][i] + row_first[x][y][i]\n",
    "                cur_result[0] = min(1,cur_result[0]) # 切成1份最多只有1种方法\n",
    "                for i in range(k):\n",
    "                    csum[x][y][i] = csum[x][y+1][i] + cur_result[i]\n",
    "                    rsum[x][y][i] = rsum[x+1][y][i] + cur_result[i]\n",
    "        return mod(cur_result[-1],10**9+7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # init\n",
    "        m,n = len(pizza),len(pizza[0])\n",
    "        col_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        row_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        rhave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        chave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        # dp\n",
    "        for x in range(m-1,-1,-1):\n",
    "            for y in range(n-1,-1,-1):\n",
    "                # cut column first\n",
    "                chave[x][y] = chave[x+1][y] or pizza[x][y]==\"A\"\n",
    "                if not chave[x][y]:\n",
    "                    col_first[x][y] = col_first[x][y+1].copy()\n",
    "                else: # 这一列有\"A\"\n",
    "                    for i in range(1,k):\n",
    "                        for yright in range(y+1,n): # 累加 “竖切第一刀后, 剩余部份的方法数”\n",
    "                            col_first[x][y][i] += dp[x][yright][i-1]\n",
    "                    col_first[x][y][0] = 1\n",
    "                # cut row first\n",
    "                rhave[x][y] = rhave[x][y+1] or pizza[x][y]==\"A\"\n",
    "                if not rhave[x][y]:\n",
    "                    row_first[x][y] = row_first[x+1][y].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        for xdown in range(x+1,m):\n",
    "                            row_first[x][y][i] += dp[xdown][y][i-1]\n",
    "                    row_first[x][y][0] = 1\n",
    "                # update dp\n",
    "                for i in range(k):\n",
    "                    dp[x][y][i] = col_first[x][y][i] + row_first[x][y][i]\n",
    "                dp[x][y][0] = min(1,dp[x][y][0]) # 切成1份最多只有1种方法\n",
    "        return mod(dp[0][0][-1],10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m,n = len(pizza),len(pizza[0])\n",
    "        col_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        row_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        rhave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        chave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        # dp\n",
    "        for x in range(m-1,-1,-1):\n",
    "            for y in range(n-1,-1,-1):\n",
    "                # cut column first\n",
    "                chave[x][y] = chave[x+1][y] or pizza[x][y]==\"A\"\n",
    "                if not chave[x][y]:\n",
    "                    col_first[x][y] = col_first[x][y+1].copy()\n",
    "                else: # 这一列有\"A\"\n",
    "                    for i in range(1,k):\n",
    "                        for yright in range(y+1,n): # 累加 “竖切第一刀后, 剩余部份的方法数”\n",
    "                            col_first[x][y][i] += dp[x][yright][i-1]\n",
    "                    col_first[x][y][0] = 1\n",
    "                # cut row first\n",
    "                rhave[x][y] = rhave[x][y+1] or pizza[x][y]==\"A\"\n",
    "                if not rhave[x][y]:\n",
    "                    row_first[x][y] = row_first[x+1][y].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        for xdown in range(x+1,m):\n",
    "                            row_first[x][y][i] += dp[xdown][y][i-1]\n",
    "                    row_first[x][y][0] = 1\n",
    "                # update dp\n",
    "                for i in range(k):\n",
    "                    dp[x][y][i] = col_first[x][y][i] + row_first[x][y][i]\n",
    "                dp[x][y][0] = min(1,dp[x][y][0]) # 切成1份最多只有1种方法\n",
    "        return mod(dp[0][0][-1],10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 1_000_000_007\n",
    "        yLen, xLen = len(pizza), len(pizza[0])\n",
    "        \n",
    "        @cache\n",
    "        def dp(curY: int, curX: int) -> List[int]:\n",
    "            if curY == yLen or curX == xLen: return []\n",
    "            \n",
    "            xHasApple = yHasApple = False\n",
    "\n",
    "            for y in range(curY, yLen):\n",
    "                if pizza[y][curX] == 'A':\n",
    "                    yHasApple = True\n",
    "                    break\n",
    "            \n",
    "            for x in range(curX, xLen):\n",
    "                if pizza[curY][x] == 'A':\n",
    "                    xHasApple = True\n",
    "                    break\n",
    "            \n",
    "            if xHasApple == yHasApple == False:\n",
    "                return dp(curY + 1, curX + 1)\n",
    "\n",
    "            if yHasApple == False:\n",
    "                return dp(curY, curX + 1)\n",
    "\n",
    "            if xHasApple == False:\n",
    "                return dp(curY + 1, curX)\n",
    "\n",
    "            res = [0] * (k + 1)\n",
    "\n",
    "            for y in range(curY + 1, yLen):\n",
    "                for i,v in enumerate(dp(y, curX)[:k]):\n",
    "                    res[i + 1] += v\n",
    "\n",
    "            for x in range(curX + 1, xLen):\n",
    "                for i,v in enumerate(dp(curY, x)[:k]):\n",
    "                    res[i + 1] += v\n",
    "                # li = dp(y, curX)\n",
    "                # if li == None: continue\n",
    "                # for i in range(0, k):\n",
    "                #     res[i + 1] += li[i]\n",
    "            \n",
    "            # for x in range(curX + 1, xLen):\n",
    "            #     li = dp(curY, x)\n",
    "            #     if li == None: continue\n",
    "            #     for i in range(0, k):\n",
    "            #         res[i + 1] += li[i]\n",
    "            \n",
    "            res[0] = 1\n",
    "            \n",
    "            return res\n",
    "\n",
    "        ans = dp(0, 0)\n",
    "        \n",
    "        # print(ans)\n",
    "\n",
    "        if ans: return ans[k - 1] % MOD\n",
    "        else: return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        def getTag(row, col, cut):\n",
    "            return str(row)+'-'+str(col)+'-'+str(cut)\n",
    "        def dfs(row, col, cut):\n",
    "            if cut == k-1:\n",
    "                if presum[n][m] - (presum[row][m]+presum[n][col]-presum[row][col]) > 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            tag = getTag(row, col, cut)\n",
    "            if tag in memo:\n",
    "                return memo[tag]\n",
    "            res = 0\n",
    "            for nrow in range(row, n):\n",
    "                if presum[nrow+1][m]-presum[row][m]-presum[nrow+1][col] + presum[row][col] > 0:\n",
    "                    res += dfs(nrow+1, col, cut+1)\n",
    "            for ncol in range(col, m):\n",
    "                if presum[n][ncol+1] - presum[n][col] - presum[row][ncol+1] + presum[row][col] > 0:\n",
    "                    res += dfs(row, ncol+1, cut+1)\n",
    "            memo[tag] = res % (10**9+7)\n",
    "            return memo[tag]\n",
    "        n, m = len(pizza), len(pizza[0])\n",
    "        presum = [[0 for _ in range(m+1)] for _ in range(n+1)]\n",
    "        memo = {}\n",
    "        for row in range(1, len(presum)):\n",
    "            for col in range(1, len(presum[0])):\n",
    "                presum[row][col] = presum[row-1][col]+presum[row][col-1]-presum[row-1][col-1]\n",
    "                if pizza[row-1][col-1] == 'A':\n",
    "                    presum[row][col] += 1\n",
    "        return dfs(0, 0, 0)\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(i, j, c):\n",
    "        #     if c == k - 1:#切了k - 1次,判断剩余披萨是否有苹果\n",
    "        #         if pre[m][n] - pre[i][n] - pre[m][j] + pre[i][j] > 0:\n",
    "        #             return 1\n",
    "        #         return 0\n",
    "        #     res = 0\n",
    "        #     for x in range(i, m):#水平切\n",
    "        #         if pre[x + 1][n] - pre[i][n] - pre[x + 1][j] + pre[i][j] > 0:\n",
    "        #             res += dfs(x + 1, j, c + 1)\n",
    "        #     for x in range(j, n):#垂直切\n",
    "        #         if pre[m][x + 1] - pre[m][j] - pre[i][x + 1] + pre[i][j] > 0:\n",
    "        #             res += dfs(i, x + 1, c + 1)\n",
    "        #     return res % (10 ** 9 + 7)\n",
    "        # m, n = len(pizza), len(pizza[0])\n",
    "        # pre = [[0 for i in range(n + 1)] for j in range(m + 1)]#前缀和\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j]\n",
    "        #         if pizza[i][j] == \"A\":#当有苹果时,区间和 + 1\n",
    "        #             pre[i + 1][j + 1] += 1\n",
    "        # print(pre)\n",
    "        # return dfs(0, 0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 1_000_000_007\n",
    "        yLen, xLen = len(pizza), len(pizza[0])\n",
    "        \n",
    "        @cache\n",
    "        def dp(curY: int, curX: int) -> List[int]:\n",
    "            if curY == yLen or curX == xLen: return None\n",
    "            \n",
    "            xHasApple = yHasApple = False\n",
    "\n",
    "            for y in range(curY, yLen):\n",
    "                if pizza[y][curX] == 'A':\n",
    "                    yHasApple = True\n",
    "                    break\n",
    "            \n",
    "            for x in range(curX, xLen):\n",
    "                if pizza[curY][x] == 'A':\n",
    "                    xHasApple = True\n",
    "                    break\n",
    "            \n",
    "            if xHasApple == yHasApple == False:\n",
    "                # return dp(curY + 1, curX + 1)\n",
    "                return dp(curY + 1, curX)\n",
    "\n",
    "            if yHasApple == False:\n",
    "                return dp(curY, curX + 1)\n",
    "\n",
    "            if xHasApple == False:\n",
    "                return dp(curY + 1, curX)\n",
    "\n",
    "            res = [0] * (k + 1)\n",
    "\n",
    "            for y in range(curY + 1, yLen):\n",
    "                li = dp(y, curX)\n",
    "                if li == None: continue\n",
    "                for i in range(0, k): res[i + 1] += li[i]\n",
    "            \n",
    "            for x in range(curX + 1, xLen):\n",
    "                li = dp(curY, x)\n",
    "                if li == None: continue\n",
    "                for i in range(0, k): res[i + 1] += li[i]\n",
    "            \n",
    "            res[0] = 1\n",
    "            \n",
    "            return res\n",
    "\n",
    "        ans = dp(0, 0)\n",
    "\n",
    "        return ans[k - 1] % MOD if ans else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # init\n",
    "        m,n = len(pizza),len(pizza[0])\n",
    "        col_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        row_first = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp = [[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        rhave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        chave = [[False]*(n+1) for _ in range(m+1)]\n",
    "        # dp\n",
    "        for x in range(m-1,-1,-1):\n",
    "            for y in range(n-1,-1,-1):\n",
    "                # cut column first\n",
    "                chave[x][y] = chave[x+1][y] or pizza[x][y]==\"A\"\n",
    "                if not chave[x][y]:\n",
    "                    col_first[x][y] = col_first[x][y+1].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        for yright in range(y+1,n):\n",
    "                            col_first[x][y][i] += dp[x][yright][i-1]\n",
    "                    col_first[x][y][0] = 1\n",
    "                # cut row first\n",
    "                rhave[x][y] = rhave[x][y+1] or pizza[x][y]==\"A\"\n",
    "                if not rhave[x][y]:\n",
    "                    row_first[x][y] = row_first[x+1][y].copy()\n",
    "                else:\n",
    "                    for i in range(1,k):\n",
    "                        for xdown in range(x+1,m):\n",
    "                            row_first[x][y][i] += dp[xdown][y][i-1]\n",
    "                    row_first[x][y][0] = 1\n",
    "                # update dp\n",
    "                for i in range(k):\n",
    "                    dp[x][y][i] = col_first[x][y][i] + row_first[x][y][i]\n",
    "                dp[x][y][0] = min(1,dp[x][y][0])\n",
    "        return mod(dp[0][0][-1],10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 1_000_000_007\n",
    "        yLen, xLen = len(pizza), len(pizza[0])\n",
    "        # grid = [[[0] * k for x in range(xLen)] for y in range(yLen)]\n",
    "        # print(grid)\n",
    "\n",
    "        @cache\n",
    "        def dp(curY: int, curX: int) -> List[int]:\n",
    "            if curY == yLen or curX == xLen: return None\n",
    "            \n",
    "            xHasApple = yHasApple = False\n",
    "\n",
    "            for y in range(curY, yLen):\n",
    "                if pizza[y][curX] == 'A':\n",
    "                    yHasApple = True\n",
    "                    break\n",
    "            \n",
    "            for x in range(curX, xLen):\n",
    "                if pizza[curY][x] == 'A':\n",
    "                    xHasApple = True\n",
    "                    break\n",
    "            \n",
    "            if xHasApple == yHasApple == False:\n",
    "                return dp(curY + 1, curX + 1)\n",
    "\n",
    "            if yHasApple == False:\n",
    "                return dp(curY, curX + 1)\n",
    "\n",
    "            if xHasApple == False:\n",
    "                return dp(curY + 1, curX)\n",
    "\n",
    "            res = [0] * (k + 1)\n",
    "\n",
    "            for y in range(curY + 1, yLen):\n",
    "                li = dp(y, curX)\n",
    "                if li == None: continue\n",
    "                for i in range(0, k):\n",
    "                    res[i + 1] += li[i]\n",
    "            \n",
    "            for x in range(curX + 1, xLen):\n",
    "                li = dp(curY, x)\n",
    "                if li == None: continue\n",
    "                for i in range(0, k):\n",
    "                    res[i + 1] += li[i]\n",
    "            \n",
    "            res[0] = 1\n",
    "            \n",
    "            return res\n",
    "\n",
    "        ans = dp(0, 0)\n",
    "        \n",
    "        # print(ans)\n",
    "\n",
    "        if ans: return ans[k - 1] % MOD\n",
    "        else: return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        def getTag(row, col, cut):\n",
    "            return str(row)+'-'+str(col)+'-'+str(cut)\n",
    "        def dfs(row, col, cut):\n",
    "            if cut == k-1:\n",
    "                if presum[n][m] - (presum[row][m]+presum[n][col]-presum[row][col]) > 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            tag = getTag(row, col, cut)\n",
    "            if tag in memo:\n",
    "                return memo[tag]\n",
    "            res = 0\n",
    "            for nrow in range(row, n):\n",
    "                if presum[nrow+1][m]-presum[row][m]-presum[nrow+1][col] + presum[row][col] > 0:\n",
    "                    res += dfs(nrow+1, col, cut+1)\n",
    "            for ncol in range(col, m):\n",
    "                if presum[n][ncol+1] - presum[n][col] - presum[row][ncol+1] + presum[row][col] > 0:\n",
    "                    res += dfs(row, ncol+1, cut+1)\n",
    "            memo[tag] = res % (10**9+7)\n",
    "            return memo[tag]\n",
    "        n, m = len(pizza), len(pizza[0])\n",
    "        presum = [[0 for _ in range(m+1)] for _ in range(n+1)]\n",
    "        memo = {}\n",
    "        for row in range(1, len(presum)):\n",
    "            for col in range(1, len(presum[0])):\n",
    "                presum[row][col] = presum[row-1][col]+presum[row][col-1]-presum[row-1][col-1]\n",
    "                if pizza[row-1][col-1] == 'A':\n",
    "                    presum[row][col] += 1\n",
    "        return dfs(0, 0, 0)\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(i, j, c):\n",
    "        #     if c == k - 1:#切了k - 1次,判断剩余披萨是否有苹果\n",
    "        #         if pre[m][n] - pre[i][n] - pre[m][j] + pre[i][j] > 0:\n",
    "        #             return 1\n",
    "        #         return 0\n",
    "        #     res = 0\n",
    "        #     for x in range(i, m):#水平切\n",
    "        #         if pre[x + 1][n] - pre[i][n] - pre[x + 1][j] + pre[i][j] > 0:\n",
    "        #             res += dfs(x + 1, j, c + 1)\n",
    "        #     for x in range(j, n):#垂直切\n",
    "        #         if pre[m][x + 1] - pre[m][j] - pre[i][x + 1] + pre[i][j] > 0:\n",
    "        #             res += dfs(i, x + 1, c + 1)\n",
    "        #     return res % (10 ** 9 + 7)\n",
    "        # m, n = len(pizza), len(pizza[0])\n",
    "        # pre = [[0 for i in range(n + 1)] for j in range(m + 1)]#前缀和\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j]\n",
    "        #         if pizza[i][j] == \"A\":#当有苹果时,区间和 + 1\n",
    "        #             pre[i + 1][j + 1] += 1\n",
    "        # print(pre)\n",
    "        # return dfs(0, 0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "\r\n",
    "    def ways(self, pizza: list[str], k: int) -> int:\r\n",
    "        MOD = 10**9 + 7\r\n",
    "        m, n = len(pizza), len(pizza[0])\r\n",
    "        col_first = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\r\n",
    "        row_first = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\r\n",
    "        dp = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\r\n",
    "        rhave = [[False] * (n + 1) for _ in range(m + 1)]\r\n",
    "        chave = [[False] * (n + 1) for _ in range(m + 1)]\r\n",
    "        # dp\r\n",
    "        for x in range(m - 1, -1, -1):\r\n",
    "            for y in range(n - 1, -1, -1):\r\n",
    "                # cut column first\r\n",
    "                chave[x][y] = chave[x + 1][y] or pizza[x][y] == \"A\"\r\n",
    "                if not chave[x][y]:\r\n",
    "                    col_first[x][y] = col_first[x][y + 1].copy()\r\n",
    "                else:  # 这一列有\"A\"\r\n",
    "                    for i in range(1, k):\r\n",
    "                        for yright in range(y + 1, n):  # 累加 “竖切第一刀后, 剩余部份的方法数”\r\n",
    "                            col_first[x][y][i] += dp[x][yright][i - 1]\r\n",
    "                    col_first[x][y][0] = 1\r\n",
    "                # cut row first\r\n",
    "                rhave[x][y] = rhave[x][y + 1] or pizza[x][y] == \"A\"\r\n",
    "                if not rhave[x][y]:\r\n",
    "                    row_first[x][y] = row_first[x + 1][y].copy()\r\n",
    "                else:\r\n",
    "                    for i in range(1, k):\r\n",
    "                        for xdown in range(x + 1, m):\r\n",
    "                            row_first[x][y][i] += dp[xdown][y][i - 1]\r\n",
    "                    row_first[x][y][0] = 1\r\n",
    "                # update dp\r\n",
    "                for i in range(k):\r\n",
    "                    dp[x][y][i] = col_first[x][y][i] + row_first[x][y][i]\r\n",
    "                dp[x][y][0] = min(1, dp[x][y][0])  # 切成1份最多只有1种方法\r\n",
    "        return dp[0][0][k - 1] % MOD\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    mod = 10 ** 9 + 7\n",
    "    n = m = s = None\n",
    "\n",
    "    @cache\n",
    "    def dfs(self, x: int, y: int, k: int):\n",
    "        if k == 1: return 1\n",
    "        v = 0\n",
    "        for i in range(x + 1, self.n + 1):\n",
    "            # 当前可以水平切\n",
    "            if self.s[x][y] > self.s[i][y] >= k - 1:\n",
    "                v += self.dfs(i, y, k - 1) % self.mod\n",
    "        # 垂直切\n",
    "        for i in range(y + 1, self.m + 1):\n",
    "            if self.s[x][y] > self.s[x][i] >= k - 1:\n",
    "                v += self.dfs(x, i, k - 1) % self.mod\n",
    "        return v % self.mod\n",
    "\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        # 预处理二维前缀和\n",
    "        n, m = len(pizza), len(pizza[0])\n",
    "        s = [[0] * (m + 2) for i in range(n + 2)]\n",
    "        # 这里的前缀和下标从1开始\n",
    "        for i in range(n, 0, -1):\n",
    "            for j in range(m, 0, -1):\n",
    "                w = 1 if pizza[i - 1][j - 1] == \"A\" else 0\n",
    "                s[i][j] = s[i + 1][j] + s[i][j + 1] - s[i + 1][j + 1] + w\n",
    "        self.n, self.m, self.s = n, m, s\n",
    "        # 由于前缀和下标从1开始所以在搜索的时候下标也是从1开始的\n",
    "        return self.dfs(1, 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        def getTag(row, col, cut):\n",
    "            return str(row)+'-'+str(col)+'-'+str(cut)\n",
    "        def dfs(row, col, cut):\n",
    "            if cut == k-1:\n",
    "                if presum[n][m] - (presum[row][m]+presum[n][col]-presum[row][col]) > 0:\n",
    "                    return 1\n",
    "                return 0\n",
    "            tag = getTag(row, col, cut)\n",
    "            if tag in memo:\n",
    "                return memo[tag]\n",
    "            res = 0\n",
    "            for nrow in range(row, n):\n",
    "                if presum[nrow+1][m]-presum[row][m]-presum[nrow+1][col] + presum[row][col] > 0:\n",
    "                    res += dfs(nrow+1, col, cut+1)\n",
    "            for ncol in range(col, m):\n",
    "                if presum[n][ncol+1] - presum[n][col] - presum[row][ncol+1] + presum[row][col] > 0:\n",
    "                    res += dfs(row, ncol+1, cut+1)\n",
    "            memo[tag] = res % (10**9+7)\n",
    "            return memo[tag]\n",
    "        n, m = len(pizza), len(pizza[0])\n",
    "        presum = [[0 for _ in range(m+1)] for _ in range(n+1)]\n",
    "        memo = {}\n",
    "        for row in range(1, len(presum)):\n",
    "            for col in range(1, len(presum[0])):\n",
    "                presum[row][col] = presum[row-1][col]+presum[row][col-1]-presum[row-1][col-1]\n",
    "                if pizza[row-1][col-1] == 'A':\n",
    "                    presum[row][col] += 1\n",
    "        return dfs(0, 0, 0)\n",
    "\n",
    "        # @lru_cache(None)\n",
    "        # def dfs(i, j, c):\n",
    "        #     if c == k - 1:#切了k - 1次,判断剩余披萨是否有苹果\n",
    "        #         if pre[m][n] - pre[i][n] - pre[m][j] + pre[i][j] > 0:\n",
    "        #             return 1\n",
    "        #         return 0\n",
    "        #     res = 0\n",
    "        #     for x in range(i, m):#水平切\n",
    "        #         if pre[x + 1][n] - pre[i][n] - pre[x + 1][j] + pre[i][j] > 0:\n",
    "        #             res += dfs(x + 1, j, c + 1)\n",
    "        #     for x in range(j, n):#垂直切\n",
    "        #         if pre[m][x + 1] - pre[m][j] - pre[i][x + 1] + pre[i][j] > 0:\n",
    "        #             res += dfs(i, x + 1, c + 1)\n",
    "        #     return res % (10 ** 9 + 7)\n",
    "        # m, n = len(pizza), len(pizza[0])\n",
    "        # pre = [[0 for i in range(n + 1)] for j in range(m + 1)]#前缀和\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j]\n",
    "        #         if pizza[i][j] == \"A\":#当有苹果时,区间和 + 1\n",
    "        #             pre[i + 1][j + 1] += 1\n",
    "        # print(pre)\n",
    "        # return dfs(0, 0, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# sum(pizza, [])\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int, res_k_num: Dict[str, int] = None) -> int:\n",
    "        if res_k_num is None:\n",
    "            res_k_num = {}\n",
    "        if not pizza:\n",
    "            return 0\n",
    "        if k == 1:\n",
    "            if 'A' not in \"\".join(pizza):\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        rows = len(pizza)\n",
    "        cols = len(pizza[0])\n",
    "\n",
    "        sum = 0\n",
    "        for i in range(1, rows):\n",
    "            if 'A' not in \"\".join(pizza[:i]):\n",
    "                sum += 0 \n",
    "            else:\n",
    "                if f'{rows-i}_{cols}_{k-1}' not in res_k_num:\n",
    "                    res_k_num[f'{rows-i}_{cols}_{k-1}'] = self.ways(pizza[i:], k-1, res_k_num)\n",
    "                sum += res_k_num[f'{rows-i}_{cols}_{k-1}']              \n",
    "        \n",
    "        for j in range(1, cols):\n",
    "            if 'A' not in \"\".join([item[:j] for item in pizza]):\n",
    "                sum += 0\n",
    "            else:\n",
    "                if f'{rows}_{cols-j}_{k-1}' not in res_k_num:\n",
    "                    res_k_num[f'{rows}_{cols-j}_{k-1}'] = self.ways([item[j:] for item in pizza], k-1, res_k_num)\n",
    "                sum += res_k_num[f'{rows}_{cols-j}_{k-1}']\n",
    "        return int(sum%(1e9 + 7))\n",
    "    \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "\n",
    "        preSum = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                preSum[i][j] = preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+(1 if pizza[i-1][j-1] == 'A' else 0)\n",
    "        @functools.lru_cache(None)\n",
    "        def check(i, j, pos, k):  # 坐标按照前缀和来，即分割前缀和矩阵\n",
    "            # print(f\"{pos}{k}:i{i},{j}:{0}\")\n",
    "            if preSum[m][n]-preSum[i][n]-preSum[m][j]+preSum[i][j] == 0:\n",
    "                # print(f\"{pos}{k}:e{i},{j}:{0}\")\n",
    "                return 0  # 没有苹果返回0\n",
    "            if k == 0:\n",
    "                # print(f\"{pos}{k}:e{i},{j}:{1}\")\n",
    "                return 1  # 切完了，剩下的一块有苹果，返回1\n",
    "\n",
    "            res = 0\n",
    "            for ti in range(i+1, m):\n",
    "                if preSum[ti][n]-preSum[i][n]-preSum[ti][j]+preSum[i][j] == 0: continue\n",
    "                res += check(ti, j, pos+\"  \", k-1)\n",
    "            for tj in range(j+1, n):\n",
    "                if preSum[m][tj]-preSum[i][tj]-preSum[m][j]+preSum[i][j] == 0: continue\n",
    "                res += check(i, tj, pos+\"  \", k-1)\n",
    "            # print(f\"{pos}{k}:e{i},{j}:{res}\")\n",
    "            return res\n",
    "\n",
    "        return check(0, 0, \"\", k-1) % ( 10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        rows, cols = len(pizza), len(pizza[0])\n",
    "        @cache\n",
    "        def dfs(x,y,t):\n",
    "            if x == rows or y == cols :\n",
    "                return 0\n",
    "            if t == 1:\n",
    "                for i in range(x,rows):\n",
    "                    for j in range(y, cols):\n",
    "                        if pizza[i][j] == 'A':\n",
    "                            return 1\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            minRow, minCol = rows, cols\n",
    "            for i in range(x,rows):\n",
    "                for j in range(y, cols):\n",
    "                    if pizza[i][j] == 'A':\n",
    "                        minRow = min(minRow, i)\n",
    "                        minCol = min(minCol, j)\n",
    "            for r in range(minRow,rows):\n",
    "                res += dfs(r+1, y, t-1)\n",
    "            for c in range(minCol,cols):\n",
    "                res += dfs(x, c+1, t-1)\n",
    "            return res\n",
    "\n",
    "        return dfs(0,0,k) % int(1e9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    cache = {}\n",
    "\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        Solution.cache.clear()\n",
    "        return self._ways(pizza, k)\n",
    "\n",
    "\n",
    "    def _ways(self, pizza: List[str], k: int) -> int:\n",
    "        if not pizza or not pizza[0]:\n",
    "            return 0\n",
    "\n",
    "        if k==1:\n",
    "            for row in pizza:\n",
    "                if row.find('A') != -1:\n",
    "                    return 1\n",
    "            return 0\n",
    "\n",
    "        cache_key = (len(pizza), len(pizza[0]), k)\n",
    "        if cache_key in Solution.cache:\n",
    "            return Solution.cache[cache_key]\n",
    "        \n",
    "\n",
    "        way_count = 0\n",
    "        \n",
    "        has_apple = False\n",
    "        for index, row in enumerate(pizza):\n",
    "            if row.find('A') != -1:\n",
    "                has_apple = True\n",
    "            if has_apple:\n",
    "                way_count += self._ways(pizza[index + 1:], k-1)\n",
    "        \n",
    "        \n",
    "        has_apple = False\n",
    "        for col_index in range(len(pizza[0])):\n",
    "            for row in pizza:\n",
    "                if row[col_index] == 'A':\n",
    "                    has_apple = True\n",
    "            if has_apple:\n",
    "                slice_pizza = [row[col_index+1:] for row in pizza]\n",
    "                way_count += self._ways(slice_pizza, k-1)       \n",
    "\n",
    "        Solution.cache[cache_key] = way_count%(10**9+7)\n",
    "        return way_count%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        mn, t = m + n, 10 ** 9 + 7\n",
    "        \n",
    "        def f(c):\n",
    "            for i in range(m - 1, -1, -1):\n",
    "                if pizza[i][c] == 'A':\n",
    "                    return i\n",
    "            return -1\n",
    "            \n",
    "        rs = [r.rfind('A') for r in pizza]\n",
    "        cs = [f(c) for c in range(n)]\n",
    "        \n",
    "        @cache\n",
    "        def f(r, c, k):\n",
    "            if k == 1:\n",
    "                return int(any(r <= cs[i] for i in range(c, n)))\n",
    "            k -= 1\n",
    "            return (sum(f(i, c, k) for i in \n",
    "            dropwhile(lambda i: c > rs[i - 1], iter(range(r + 1, min(m, mn - k - c))))) + sum(f(r, i, k) for i in \n",
    "            dropwhile(lambda i: r > cs[i - 1], iter(range(c + 1, min(n, mn - k - r)))))) % t\n",
    "            \n",
    "        return f(0, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + int(pizza[i - 1][j - 1] == 'A')\n",
    "        \n",
    "        @cache\n",
    "        def f(i: int, j: int, cnt: int) -> int:\n",
    "            if i >= m or j >= n:\n",
    "                return 0\n",
    "            if cnt >= k - 1:\n",
    "                if pre[m][n] - pre[m][j] - pre[i][n] + pre[i][j] > 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            res = 0\n",
    "            for x in range(i + 1, m):\n",
    "                if pre[x][n] - pre[x][j] - pre[i][n] + pre[i][j] > 0:\n",
    "                    res = (res + f(x, j, cnt + 1)) % MOD\n",
    "            for y in range(j + 1, n):\n",
    "                if pre[m][y] - pre[m][j] - pre[i][y] + pre[i][j] > 0:\n",
    "                    res = (res + f(i, y, cnt + 1)) % MOD\n",
    "            return res\n",
    "        \n",
    "        return f(0, 0, 0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m,n = len(pizza), len(pizza[0])\n",
    "        suf = [[0] * (n+1) for _ in range(m+1)]\n",
    "\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                suf[i][j] = int(pizza[i][j] == 'A') + suf[i+1][j] + suf[i][j+1] - suf[i+1][j+1]\n",
    "        # print(suf)\n",
    "        if suf[0][0] ==0:\n",
    "            return 0\n",
    "        MOD=10**9+7\n",
    "        @cache\n",
    "        def dfs(i,j,left):\n",
    "            if left == 1:\n",
    "                return 1\n",
    "            ans = 0\n",
    "            for nx in range(i+1,m):\n",
    "                if suf[nx][j] < suf[i][j] and suf[nx][j]>=left-1:\n",
    "                    ans += dfs(nx,j,left-1)\n",
    "            for ny in range(j+1,n):\n",
    "                if suf[i][ny] < suf[i][j] and suf[i][ny]>=left-1:\n",
    "                    ans += dfs(i,ny, left-1)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0,0,k) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        def check(rl: int, rr: int, cl: int, cr: int) -> bool:\n",
    "            for x in range(rl, rr):\n",
    "                for y in range(cl, cr):\n",
    "                    if pizza[x][y] == 'A':\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        @cache\n",
    "        def dfs(row: int, col: int, cnt: int) -> int:\n",
    "            if cnt == 0:\n",
    "                return int(check(row, m, col, n))\n",
    "            res = 0\n",
    "            for i in range(row + 1, m):\n",
    "                if check(row, i, col, n):\n",
    "                    res += dfs(i, col, cnt - 1)\n",
    "            for j in range(col + 1, n):\n",
    "                if check(row, m, col, j):\n",
    "                    res += dfs(row, j, cnt - 1)\n",
    "            return res\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        return dfs(0, 0, k - 1) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        ms = MatrixSum(pizza)\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        @cache\n",
    "        def dfs(c, i, j):\n",
    "            if c == 0:\n",
    "                return 1 if ms.query(i, j, m, n) else 0\n",
    "            res = 0\n",
    "            for j2 in range(j + 1, n):\n",
    "                if ms.query(i, j, m, j2):\n",
    "                    res += dfs(c - 1, i, j2)\n",
    "            for i2 in range(i + 1, m):\n",
    "                if ms.query(i, j, i2, n):\n",
    "                    res += dfs(c - 1, i2, j)\n",
    "            return res % MOD\n",
    "        return dfs(k - 1, 0, 0)\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + (x == 'A')\n",
    "        self.s = s\n",
    "\n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "            return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        postsum = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                postsum[i][j] = postsum[i+1][j]+postsum[i][j+1]-postsum[i+1][j+1]+(pizza[i][j]=='A')\n",
    "        @cache\n",
    "        def dp(x,y,k):\n",
    "            MOD = 10**9+7\n",
    "            nonlocal postsum, m, n\n",
    "            if postsum[x][y]<k:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return 1\n",
    "            res = 0\n",
    "            for i in range(x+1, m):\n",
    "                if postsum[x][y]>postsum[i][y]:\n",
    "                    res+=dp(i,y,k-1)\n",
    "            for j in range(y+1, n):\n",
    "                if postsum[x][y]>postsum[x][j]:\n",
    "                    res+=dp(x,j,k-1)\n",
    "            return res%MOD\n",
    "        return dp(0,0,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        rows = len(pizza)\n",
    "        cols = len(pizza[0])\n",
    "\n",
    "        def countApple(r, c):\n",
    "            if pizza[r][c] == 'A':\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "\n",
    "        # construct apple counts\n",
    "        counts = []\n",
    "        for i in range(rows):\n",
    "            counts.append([])\n",
    "            for j in range(cols):\n",
    "                counts[i].append(0)\n",
    "        # count \n",
    "        counts[rows - 1][cols - 1] = countApple(rows -1, cols - 1)\n",
    "\n",
    "        i = rows - 2\n",
    "        j = cols - 2\n",
    "        while i >= 0:\n",
    "            counts[i][cols -1] = counts[i + 1][cols - 1] + countApple(i, cols - 1)\n",
    "            i -= 1\n",
    "        while j >= 0:\n",
    "            counts[rows - 1][j] = counts[rows - 1][j + 1] + countApple(rows - 1, j)\n",
    "            j -= 1\n",
    "\n",
    "        i = rows - 2\n",
    "        while i >= 0:\n",
    "            j = cols - 2\n",
    "            while j >= 0:\n",
    "                counts[i][j] = counts[i + 1][j] + counts[i][j + 1] - counts[i + 1][j + 1] + countApple(i, j)\n",
    "                j -= 1\n",
    "            i -= 1\n",
    "        @cache\n",
    "        def countPlan(r, c, k):\n",
    "            plan = 0\n",
    "            count = counts[r][c]\n",
    "            if k == 1 and count > 0:\n",
    "                return 1\n",
    "            elif k > count:\n",
    "                return 0\n",
    "            else:\n",
    "                for i in range(r + 1, rows):\n",
    "                    add_count = countPlan(i, c, k - 1)\n",
    "                    if count - counts[i][c] > 0 and add_count > 0:\n",
    "                        plan += add_count\n",
    "                for j in range(c + 1, cols):\n",
    "                    add_count = countPlan(r, j, k - 1)\n",
    "                    if count - counts[r][j] > 0 and add_count > 0:\n",
    "                        plan += add_count\n",
    "            return plan\n",
    "\n",
    "        return countPlan(0, 0, k) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        \n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        pre_sum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i+1][j+1] = pre_sum[i+1][j] + pre_sum[i][j+1] + (pizza[i][j] == 'A') - pre_sum[i][j]\n",
    "        # for x in pre_sum:\n",
    "        #     print(x)\n",
    "\n",
    "        def check(x1, y1, x2, y2):\n",
    "            return pre_sum[x2+1][y2+1] - pre_sum[x2+1][y1] - pre_sum[x1][y2+1] + pre_sum[x1][y1] >= 1\n",
    "\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(x1, y1, x2, y2, k):\n",
    "        #     if k == 0: return int(check(x1, y1, x2, y2)) # 最后一块也需要有苹果\n",
    "        #     res = 0\n",
    "        #     for y in range(y1, y2):\n",
    "        #         if check(x1, y1, x2, y):\n",
    "        #             res = (res + dfs(x1, y+1, x2, y2, k-1)) % MOD\n",
    "        #     for x in range(x1, x2):\n",
    "        #         if check(x1, y1, x, y2):\n",
    "        #             res = (res + dfs(x+1, y1, x2, y2, k-1)) % MOD\n",
    "        #     return res % MOD\n",
    "\n",
    "\n",
    "        # return dfs(0, 0, m-1, n-1, k-1)\n",
    "\n",
    "        # 观察到，递归过程中，x2,y2的值并没有变化，固定为m-1和n-1\n",
    "\n",
    "        @cache\n",
    "        def dfs(x1, y1, k):\n",
    "            if k == 0: return int(check(x1, y1, m-1, n-1)) # 最后一块也需要有苹果\n",
    "            res = 0\n",
    "            for y in range(y1, n-1):\n",
    "                if check(x1, y1, m-1, y):\n",
    "                    res = (res + dfs(x1, y+1, k-1)) % MOD\n",
    "            for x in range(x1, m-1):\n",
    "                if check(x1, y1, x, n-1):\n",
    "                    res = (res + dfs(x+1, y1, k-1)) % MOD\n",
    "            return res\n",
    "\n",
    "\n",
    "        return dfs(0, 0, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        \"\"\"\n",
    "        :param pizza:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + (pizza[i][j] == 'A')\n",
    "\n",
    "        def get(x1, y1, x2, y2):\n",
    "            return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1]\n",
    "        if pre[-1][-1] == 0:\n",
    "            return 0\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(cutted, cur_r, cur_c):\n",
    "            if cutted == k:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for i in range(cur_r, m):\n",
    "                if get(cur_r, cur_c, i, n - 1) and get(i + 1, cur_c, m - 1, n - 1):\n",
    "                    cnt += get_cnt(cutted + 1, i + 1, cur_c)\n",
    "            for j in range(cur_c, n):\n",
    "                if get(cur_r, cur_c, m - 1, j) and get(cur_r, j + 1, m - 1, n - 1):\n",
    "                    cnt += get_cnt(cutted + 1, cur_r, j + 1)\n",
    "            return cnt\n",
    "\n",
    "        return get_cnt(1, 0, 0) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1444 lang=python3\n",
    "#\n",
    "# [1444] 切披萨的方案数\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "    # def ways1(self, pizza: List[str], mx: int) -> int:\n",
    "    #     MOD = 10 ** 9 + 7\n",
    "    #     # 首先要确定怎么切，如果是横着切，上面的没了，剩下的就是下面的披萨，方案数就是切下面披萨的方案数\n",
    "    #     # 如果是竖着切，那么左边的没了，剩下的就是右边的披萨，方案数就是切右边披萨的方案数\n",
    "    #     # f[i][j]代表以i, j为顶点的披萨的方案数\n",
    "    #     # 采用二维前缀和进行优化\n",
    "    #     # 二维前缀和进行预处理\n",
    "    #     m, n = len(pizza), len(pizza[0])\n",
    "    #     pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "    #     for i in range(m):\n",
    "    #         for j in range(n):\n",
    "    #             pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + (1 if pizza[i][j] == 'A' else 0)\n",
    "    #     def check(x1, y1, x2, y2):\n",
    "    #         return pre[x2 + 1][y2 + 1] - pre[x2 + 1][y1] - pre[x1][y2 + 1] + pre[x1][y1]\n",
    "    #     @cache\n",
    "    #     def dfs(i, j, cnt):\n",
    "    #         # 如果该顶点后面的pizza的苹果数目为1，代表无法再次切分，直接返回1\n",
    "    #         if cnt == 0:\n",
    "    #             if check(i, j, m - 1, n - 1):\n",
    "    #                 return 1\n",
    "    #             return 0\n",
    "    #         res = 0\n",
    "    #         # 横着切\n",
    "    #         for k in range(i + 1, m):\n",
    "    #             if check(i, j, k - 1, n - 1) and check(k, j, m - 1, n - 1):\n",
    "    #                 res = (res + dfs(k, j, cnt - 1)) % MOD\n",
    "    #         # 竖着切\n",
    "    #         for k in range(j + 1, n):\n",
    "    #             if check(i, j, m - 1, k - 1) and check(i, k, m - 1, n - 1):\n",
    "    #                 res = (res + dfs(i, k, cnt - 1)) % MOD\n",
    "    #         return res\n",
    "    #     # 最多切k-1刀\n",
    "    #     return dfs(0, 0, mx - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "        def ways(self, pizza: List[str], mx: int) -> int:\n",
    "            MOD = 10 ** 9 + 7\n",
    "            m, n = len(pizza), len(pizza[0])\n",
    "            preSum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j] + (1 if pizza[i][j] == 'A' else 0)\n",
    "            def check(x2, y2, x1, y1):\n",
    "                return preSum[x1 + 1][y1 + 1] - preSum[x2][y1 + 1] - preSum[x1 + 1][y2] + preSum[x2][y2]\n",
    "            @cache\n",
    "            def dfs(x, y, cnt):\n",
    "                if cnt == 0:\n",
    "                    if check(x, y, m - 1, n - 1):\n",
    "                        return 1\n",
    "                    return 0\n",
    "                res = 0\n",
    "                for dx in range(x, m - 1):\n",
    "                    if check(x, y, dx, n - 1):\n",
    "                        res = (res + dfs(dx + 1, y, cnt - 1)) % MOD\n",
    "                for dy in range(y, n - 1):\n",
    "                    if check(x, y, m - 1, dy):\n",
    "                        res = (res + dfs(x, dy + 1, cnt - 1)) % MOD\n",
    "                return res\n",
    "            return dfs(0, 0, mx - 1)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        MOD = 10**9 + 7\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + (pizza[i][j] == 'A')\n",
    "        # 左上(x2, y2) 右下(x1, y1)\n",
    "        def query(x1, y1, x2, y2):\n",
    "            return s[x1 + 1][y1 + 1] - s[x2][y1 + 1] - s[x1 + 1][y2] + s[x2][y2]\n",
    "        # 左上角为(i, j)，还要且c刀\n",
    "        @cache\n",
    "        def get(i, j, c) -> int:\n",
    "            if c == 0:\n",
    "                return 0 if query(m - 1, n - 1, i, j) == 0 else 1\n",
    "            res = 0\n",
    "            #横切\n",
    "            for ii in range(i + 1, m):\n",
    "                if query(ii - 1, n - 1, i, j):\n",
    "                    res += get(ii, j, c - 1)\n",
    "            for jj in range(j + 1, n):\n",
    "                if query(m - 1, jj - 1, i, j):\n",
    "                    res += get(i, jj, c - 1)\n",
    "            return res % MOD\n",
    "        return get(0, 0, k - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=1444 lang=python3\n",
    "#\n",
    "# [1444] 切披萨的方案数\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "    # def ways1(self, pizza: List[str], mx: int) -> int:\n",
    "    #     MOD = 10 ** 9 + 7\n",
    "    #     # 首先要确定怎么切，如果是横着切，上面的没了，剩下的就是下面的披萨，方案数就是切下面披萨的方案数\n",
    "    #     # 如果是竖着切，那么左边的没了，剩下的就是右边的披萨，方案数就是切右边披萨的方案数\n",
    "    #     # f[i][j]代表以i, j为顶点的披萨的方案数\n",
    "    #     # 采用二维前缀和进行优化\n",
    "    #     # 二维前缀和进行预处理\n",
    "    #     m, n = len(pizza), len(pizza[0])\n",
    "    #     pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "    #     for i in range(m):\n",
    "    #         for j in range(n):\n",
    "    #             pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j] + (1 if pizza[i][j] == 'A' else 0)\n",
    "    #     def check(x1, y1, x2, y2):\n",
    "    #         return pre[x2 + 1][y2 + 1] - pre[x2 + 1][y1] - pre[x1][y2 + 1] + pre[x1][y1]\n",
    "    #     @cache\n",
    "    #     def dfs(i, j, cnt):\n",
    "    #         # 如果该顶点后面的pizza的苹果数目为1，代表无法再次切分，直接返回1\n",
    "    #         if cnt == 0:\n",
    "    #             if check(i, j, m - 1, n - 1):\n",
    "    #                 return 1\n",
    "    #             return 0\n",
    "    #         res = 0\n",
    "    #         # 横着切\n",
    "    #         for k in range(i + 1, m):\n",
    "    #             if check(i, j, k - 1, n - 1) and check(k, j, m - 1, n - 1):\n",
    "    #                 res = (res + dfs(k, j, cnt - 1)) % MOD\n",
    "    #         # 竖着切\n",
    "    #         for k in range(j + 1, n):\n",
    "    #             if check(i, j, m - 1, k - 1) and check(i, k, m - 1, n - 1):\n",
    "    #                 res = (res + dfs(i, k, cnt - 1)) % MOD\n",
    "    #         return res\n",
    "    #     # 最多切k-1刀\n",
    "    #     return dfs(0, 0, mx - 1)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "        def ways(self, pizza: List[str], mx: int) -> int:\n",
    "            MOD = 10 ** 9 + 7\n",
    "            m, n = len(pizza), len(pizza[0])\n",
    "            preSum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    preSum[i + 1][j + 1] = preSum[i + 1][j] + preSum[i][j + 1] - preSum[i][j] + (1 if pizza[i][j] == 'A' else 0)\n",
    "            def check(x2, y2, x1, y1):\n",
    "                return preSum[x1 + 1][y1 + 1] - preSum[x2][y1 + 1] - preSum[x1 + 1][y2] + preSum[x2][y2]\n",
    "            @cache\n",
    "            def dfs(x, y, cnt):\n",
    "                if cnt == 0:\n",
    "                    if check(x, y, m - 1, n - 1):\n",
    "                        return 1\n",
    "                    return 0\n",
    "                res = 0\n",
    "                for dx in range(x, m - 1):\n",
    "                    if check(x, y, dx, n - 1):\n",
    "                        res = (res + dfs(dx + 1, y, cnt - 1)) % MOD\n",
    "                for dy in range(y, n - 1):\n",
    "                    if check(x, y, m - 1, dy):\n",
    "                        res = (res + dfs(x, dy + 1, cnt - 1)) % MOD\n",
    "                return res\n",
    "            return dfs(0, 0, mx - 1)\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        \"\"\"\n",
    "        :param pizza:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre[i + 1][j + 1] = pre[i][j + 1] + pre[i + 1][j] - pre[i][j] + (pizza[i][j] == 'A')\n",
    "\n",
    "        def get(x1, y1, x2, y2):\n",
    "            return pre[x2 + 1][y2 + 1] - pre[x1][y2 + 1] - pre[x2 + 1][y1] + pre[x1][y1]\n",
    "            \n",
    "        if pre[-1][-1] == 0:\n",
    "            return 0\n",
    "        @lru_cache(None)\n",
    "        def get_cnt(cutted, cur_r, cur_c):\n",
    "            if cutted == k:\n",
    "                return 1\n",
    "            cnt = 0\n",
    "            for i in range(cur_r, m):\n",
    "                if get(cur_r, cur_c, i, n - 1) and get(i + 1, cur_c, m - 1, n - 1):\n",
    "                    cnt += get_cnt(cutted + 1, i + 1, cur_c)\n",
    "            for j in range(cur_c, n):\n",
    "                if get(cur_r, cur_c, m - 1, j) and get(cur_r, j + 1, m - 1, n - 1):\n",
    "                    cnt += get_cnt(cutted + 1, cur_r, j + 1)\n",
    "            return cnt\n",
    "\n",
    "        return get_cnt(1, 0, 0) % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        rows, cols = len(pizza), len(pizza[0])\n",
    "        \n",
    "        # 计算前缀和\n",
    "        prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]\n",
    "        for r in range(rows-1, -1, -1):\n",
    "            for c in range(cols-1, -1, -1):\n",
    "                prefix_sum[r][c] = prefix_sum[r+1][c] + prefix_sum[r][c+1] - prefix_sum[r+1][c+1] + (pizza[r][c] == 'A')\n",
    "        \n",
    "        # 递归的动态规划函数\n",
    "        memo = {}\n",
    "        def dp(r, c, k):\n",
    "            if prefix_sum[r][c] == 0:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            if (r, c, k) in memo:\n",
    "                return memo[(r, c, k)]\n",
    "            \n",
    "            ans = 0\n",
    "            # 水平切\n",
    "            for nr in range(r+1, rows):\n",
    "                if prefix_sum[r][c] - prefix_sum[nr][c] > 0:\n",
    "                    ans += dp(nr, c, k-1)\n",
    "                    ans %= MOD\n",
    "            # 垂直切\n",
    "            for nc in range(c+1, cols):\n",
    "                if prefix_sum[r][c] - prefix_sum[r][nc] > 0:\n",
    "                    ans += dp(r, nc, k-1)\n",
    "                    ans %= MOD\n",
    "            \n",
    "            memo[(r, c, k)] = ans\n",
    "            return ans\n",
    "        \n",
    "        return dp(0, 0, k-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ways(self, pizza: List[str], k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        m, n = len(pizza), len(pizza[0])\n",
    "        pizaa = [[pizza[i][j] for i in range(m)] for j in range(n)]\n",
    "        @cache\n",
    "        def dfs(row, col, cut):\n",
    "            if row+1==m and col+1==n and cut>0:\n",
    "                return 0\n",
    "            if cut == 0:\n",
    "                for i in range(row, m):\n",
    "                    for j in range(col, n):\n",
    "                        if pizza[i][j] == 'A':\n",
    "                            return 1\n",
    "                return 0\n",
    "            ans, rf, cf = 0, False, False\n",
    "            for i in range(row, m-1):\n",
    "                if not rf and 'A' in pizza[i][col:]:\n",
    "                    rf = True\n",
    "                if rf:\n",
    "                    ans += dfs(i+1, col, cut-1)\n",
    "            for i in range(col, n-1):\n",
    "                if not cf and 'A' in pizaa[i][row:]:\n",
    "                    cf = True\n",
    "                if cf:\n",
    "                    ans += dfs(row, i+1, cut-1)\n",
    "            print(row, col, cut, ans)\n",
    "            return ans%mod\n",
    "        return dfs(0, 0, k-1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
